第1个回答 2020-01-25
1.1979 Red and Black
描述：有黑色和红色的瓷砖，1个男人站在黑色的瓷砖上，只能上下左右向黑色的瓷砖移动，现在想知道到最后他可以达到几个瓷砖。
输入：宽度W，高度H，'.'黑色砖块，'#'红色砖块，@男人所在的位置
输出：能到达的砖块数，包括一开始自己所在的位置。
解法：就是一个简单的宽搜。第一题，贴个代码仔细说一下。
#include<iostream>
#include<memory.h>
using namespace std;
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};//分别代表四个行进的方向，代表左右上下
char arr[25][25];//根据题意，读入初始的位置，最大的是20，多申请几个保险。
struct node
{
int x,y,step;
}queue[25*25];//分别代表坐标xy，和这个是第几步
int vis[25][25];//代表是否走过这个地方。
int w,h;
int bfs(int p,int q){
memset(vis,0,sizeof(vis));
int i,a,b,top,t;
node temp;
top=-1;
t=-1;
t++;
vis[p][q]=1;
queue[t].x= p;
queue[t].y=q;//初始化队列
queue[t].step=1;//塞入队列；
while(t!=top){//队列不为空；
top++;
temp.x=queue[top].x;//pop出队列，出第一个
temp.y=queue[top].y;
for(i=0;i<4;i++){
a=temp.x+dir[i][0];
b=temp.y+dir[i][1];
if(a>=0&&a<w&&b>=0&&b<h&&arr[a][b]!='#'&&vis[a][b]==0)
{
t++;
queue[t].x=a;
queue[t].y=b;
queue[t].step=queue[t-1].step+1;//可以走时，入队；
vis[a][b]=1;
}
}
}
return queue[t].step;
}
int main(){
int i,j,count,a,b;
while(scanf("%d%d",&h,&w)!=EOF)
{
if(!h&&!w)
break;
for(i=0;i<w;i++){
scanf("%s",&arr[i]);
for(j=0;j<h;j++)
if(arr[i][j]=='@'){
a=i;
b=j;
}
}
count=bfs(a,b);
printf("%d\n",count);
}
return 0;
}
2.1562 Oil Deposits/2386 Lake Counting
解释：两题类似，都是利用宽搜来找有几个湖泊的。解法和上题略有不同，首先是方向，原先是上下左右4个方向，现在要变成上下左右以及对角线的4个，一共是8个方向。其次就是，上题只有1个起始点，问最多能走几步，这里是问有几个湖泊，只要顺序找出起始点，如果该起始点未被访问，则便利该点能够到达的所有位置，全部置为访问过，如此反复，只要最后计算这么宽搜了几次就可以了。
3.1915/2243Knight Moves
解释：就是要移动象棋里的骑士，首行给出case数，每个case有3行，棋盘大小，骑士的起始位置，骑士要到的位置。典型的宽搜题，换汤不换药，就是把移动的方向改成了骑士可以移动的方向。int dir[8][2]={{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}};
还有一个地方就是原先的queue[t].step=queue[t-1].step+1;要改成que[t].step=queue[top].step+1，因为需要的是几步而不是最多能走几步，能走几步需要的是能入队列的长度，而需要几步，只是需要那一条线需要几步就可以了。走到就直接退出。
1915和2243就是输入输出个数不一样，其他基本一样，注意，1915有可能走不到，输出0。
4.3278 Catch That Cow
解释：你要去抓猫，每次可以从x到x+1，或者x-1或者2*x，问最少几步可以抓到猫。
解法：本来没想清楚，后来发现其实就是个宽搜的问题，只不过从原先的四个方向的移动一步变成了移动向前一步向后一步，移动2x步，这样的。
文章最后发布于: 2016-11-13