2176仙岛求药 中等BFS(注释很详细)

解题思路:经典的BFS.

注意事项:关于BFS/DFS我已经写过几篇题解了,这里就不再啰嗦了.

              对于DFS/BFS特性的说明与比较,我放在了我的以下两篇题解中,有兴趣可以看看.

              1.2174Lake Counting 简单BFS(注释很详细)

              2.2177走迷宫 简单BFS(注释很详细)

参考代码:

#include<bits/stdc++.h>

using namespace std;

int M,N;

char E[21][21];
//地图

int book[21][21];
//记录是否走过

struct Point
{
	int x;
	int y;
	int cnt;//记录步数
};
//点

queue<Point> que;
//点的队列

Point loc,temp;
//临时点

int i,j,k;

int Next[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
//方向数组

int nx,ny;

int flag,flag2;
//用于快速退出循环

int main()
{
	while(scanf("%d %d",&M,&N) != EOF)
	{
		
		//判断是否退出循环
		if(M == N && M == 0)
		{
			break;
		}
		
		//因为要多组输入,所以每次都要队列置空
		while(!que.empty())
		{
			que.pop();
		}
		
		//book数组也要置空
		memset(book,0,sizeof(int)*441);
		
		//flag置空
		flag = 0;
		flag2 = 0;
		
		//读入地图
		for(i = 1; i <= M; i++)
		{
			scanf("%s",&E[i][1]);
		}
		
		//扫描地图
		for(i = 1; i <=M; i++)
		{
			for(j = 1; j <= N; j++)
			{
				//找到起点
				if(E[i][j] == '@')
				{
					//剪枝,原因起点只有一个,找到了的话就不用再找了
					flag2 = 1;
					
					//用loc储存起点的信息,然后加入队列,并且标记起点走过
					loc.x = i;
					loc.y = j;
					loc.cnt = 0;//初始化为0步
					book[i][j] = 1;
					que.push(loc);
					
					/*BFS关键代码:*/
					while(que.empty() != 1)
					{
						
						//取队首元素,然后pop它
						loc = que.front();
						que.pop();
						
						//对于每个方向都要试一下
						for(k = 0; k <=3; k++)
						{
							nx = loc.x + Next[k][0];
							ny = loc.y + Next[k][1];
							
							//如果这个方向没有越界且没有走过并且是路'.'或者终点'*'时
							if(nx >= 1 && nx <= M && ny >= 1 && ny <= N
							&& (E[nx][ny] == '.'|| E[nx][ny] == '*') && book[nx][ny] == 0)
							{
								
								//就走过去,并且标记走过
								book[nx][ny] = 1;
								
								//将该点信息记录到temp,然后加入队列中
								temp.x = nx;
								temp.y = ny;
								
								//步数+1
								temp.cnt = loc.cnt+1;
								que.push(temp);
								
								//如果已经找到终点,那temp里就已经记录了终点的信息了,那就可以快速退出了
								if(E[nx][ny] == '*')
								{
									flag = 1;
									break;
								}
							}
						}
						if(flag == 1)
						{
							break;
						}
					}
				}
				if(flag == 1 || flag2 == 1)
				{
					break;
				}
			}
			if(flag == 1 || flag2 == 1)
			{
				break;
			}
		}
		
		//如果是快速退出的,那么最后队列就不为空,那么走过时候temp里的就是终点的信息
		if(que.empty())
		{
			cout << "-1" << endl;
		}
		//如果队列为空了,就是说到最后都没有快速退出,就是说没有找到终点,所以输出-1
		else
		{
			cout << temp.cnt << endl;
		}
	}
	
	return 0;
}