2022.1.11 学习总结

2022.1.11 学习总结

今天完成了三道洛谷上的搜索题，分别是：“马的遍历 - 洛谷”、“奇怪的电梯 - 洛谷”以及“[COCI2008-2009#2] PERKET - 洛谷”

题目：

马的遍历

 刚看到这道题我还以为和“迷宫 - 洛谷”那道题一样，然后才发现，，，居然是按象棋里面的“马”的行进方式走（不会下象棋的我表示一脸懵）

了解了一下“马”的行进方式，可以写出行进方向数组，如下图：

明白了题意后就很容易可以想到，在这里用bfs无疑是上好的方案

所以我们先定义一个结构体，包含三个成员变量，分别是横坐标，纵坐标以及当前步数

 

这里需要注意一下，因为在bfs中，需要用结构体数组记录某一点的所有扩展点（从某个固定的点向各个方向可以得到的点），因此为了保证不会数据溢出，需要把这个结构体数组开大些。

然后就是很常规的 *** 作了：先将起始点压入队列并标记为“已走”，再循环遍历已知点的扩展点，记录到达每个点要用到步数，按要求输出就好了

#include
int next[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{1,-2},{-1,-2}};//上：右、左//下： 右、左//右：上、下//左： 上，下
int n,m,starx,stary;
int a[500][500];//存放到达该点的步数
struct abc 
{
	int x;
	int y;
	int step;//当前步数 
 }que[160010];//扩展点数不会超过400*400
 int main()
 {
 	int head=1,tail=1;
 	scanf("%d %d %d %d",&n,&m,&starx,&stary);
 	int i,j;
 	for(i=1;i<=n;i++)
 	for(j=1;j<=m;j++)
 	a[i][j]=-1;//先将所有点标为“未到” 
 	a[starx][stary]=0;//将起始点标为0
	 que[tail].x=starx;//将起始点压入队列 
	 que[tail].y=stary;
	 que[tail].step=0;
	 tail++;
	 while(head < tail)
    {
	 	int tx,ty;
	 	for(i=0;i<8;i++)
	 	{
	 		tx=que[head].x+next[i][0];
	 		ty=que[head].y+next[i][1];
	 		if(tx < 1 || tx > n || ty < 1 || ty > m )
	 		continue;
	 		que[tail].x=tx;
	 		que[tail].y=ty;
	 		que[tail].step=que[head].step+1;
	 		if(a[tx][ty] != -1)
	 		continue;
	 		a[tx][ty]=que[tail].step;
	 		tail++;
	    }
	    head++;
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		printf("%-5d",a[i][j]);
		if(i != n)
		printf("n");
	}
 	return 0;
  } 

这里一定一定要记得：输出是有格式的！！

“（左对齐，宽 5 格，不能到达则输出 -1）”

就是要用（printf("%-5d",a[i][j])）输出

（我因为没注意到这个又错了好多次。。）

题目：

奇怪的电梯

 这题不难，类似于只有两个方向的“迷宫 - 洛谷”题（话说迷宫这题是真的很经典了），不过还有个额外的 *** 作：“剪枝”。就是把多余的没用的部分剔除，使程序能够更快地运行，专业一点的说法是

 所以写出来就是

#include
#include
#include
int n,A,B,flag=999999;//有n层楼。从A楼开始，目的地到B楼
int  storey[10000],storey2[20000];//storey[]存储当层电梯的可移动楼层数，storey2[]表示是否已到达过这个楼层（同样的楼层无需重复考虑） 
int min (int a,int b)
{
	return (a>b?b:a);
}
void dfs(int x,int temp) 
{
    if(x==B) 
	{
	//达到目标 
        flag=min(flag,temp);
        return ;
    }
    else
    {
    	if(temp < flag )
    	{
    storey2[x]=1;//标记已到的x层，防止重复考虑相同楼层 
    if( (x+storey[x]) <= n &&storey2[x+storey[x]]==0)
	{
//		if(storey2[x+storey[x]]==0) 
//		{
		dfs(x+storey[x],temp+1);
//	    }
	}
    if( (x-storey[x]) >= 1 && storey2[x-storey[x]]==0)
	{
//		if(storey2[x-storey[x]]==0) 
//		{
		dfs(x-storey[x],temp+1);
//	    }
	}
    storey2[x]=0;//回溯 
    return ;
    }
  }
}
int main() 
{
	int i,j;
    scanf("%d %d %d",&n,&A,&B);
    for(i=1; i<=n; i++) 
	{
        scanf("%d",&storey[i]);
    }
    //printf("%d",storey2[b]);
    dfs(A,0);
    	//storey2[a]=1;
	//printf("%d",storey2[b]);
    if(flag==999999)
	printf("-1");
    else 
	printf("%d",flag);
    return 0;
}

题目：

PERKET

这题也就是一道很普通的dfs题罢了，为了方便，我定义了一个结构体来存储每种配料的酸甜度，然后就可以直接按你所想的那样直接递归了

#include
#include
int n,za=1,zs=0,ans=99999999;//za表示总酸度(酸度之积），zs表示总甜度（甜度之和），ans表示两者的绝对差 
struct abc
{
	int acid;
	int sweet;
}a[20];
void dfs(int k)
{
	if(k >= n)
	return ;
	else
   { 
	za*=a[k].acid;
	zs+=a[k].sweet;
	if(ans > abs (za-zs))
	ans=abs(za-zs);
	dfs(k+1);//由0到n-1个配料逐个试探其酸度甜度绝对差
	za/=a[k].acid;
	zs-=a[k].sweet;
	dfs(k+1);
   }
}
int main()
{
	int i,j;
	scanf("%d",&n);
	for(i=0;i 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5702665.html