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

解题思路: 1.经典的BFS/DFS问题.

               2.与 第2171题:细胞 差不多,但是由于我那个题用的DFS,所以这个题就用BFS.

多说一点:1.DFS的递归函数可以很简单地编写,也更清晰明了,所以更适合解决这种搜索问题.

               2.并且BFS因为需要将每个状态依次加入队列中(这里是坐标),所以需要与状态数成正比的内存空间,

                  而DFS需要的内存空间与递归深度成正比,而一般情况下递归深度要低于状态数,所以可以认为DFS更省空间

               3.求最短路径经常使用DFS

注意事项:1.是八个方向,不要弄成四个了.

参考代码:

#include<bits/stdc++.h>

using namespace std;

int N,M;

int i,j,k;

char E[1005][115];
//记录地图

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

pair<int,int> loc,temp;
//用于记录坐标

queue< pair<int,int> > que;
//坐标队列

int cnt;
//用于统计水坑数量

int Next[8][2] = {{0,-1},{-1,0},{0,1},{1,0},{-1,-1},{1,-1},{-1,1},{1,1}};
//对应八个方向

int nx,ny;
//下一步的坐标

int main()
{
	
	scanf("%d %d",&N,&M);
	
	//读入地图
	for(i = 1; i <= N; i++)
	{
		scanf("%s",&E[i][1]);
	}
	
	//遍历地图
	for(i = 1; i <= N;i++)
	{
		for(j = 1; j <= M; j++)
		{
			//如果找到了水坑,就把它变成干燥处,然后纳入队列中,同时总水坑数量加一
			if(E[i][j] == 'W' && book[i][j] == 0)
			{
				cnt++;
				book[i][j] = 1;
				E[i][j] = '.';
				
				//用pair类型的变量loc记录坐标加入队列中
				loc.first = i;
				loc.second = j;
				que.push(loc);
				
				//当队列不为空就一直循环
				while(que.empty() != 1)
				{
					//首先从队列中取一个元素出来给loc,然后就让他pop出队列
					loc = que.front();
					que.pop();
					
					for(k = 0; k <= 7; k++)
					{
						//看是否有八连通的积水
						nx = loc.first + Next[k][0];
						ny = loc.second + Next[k][1];
						
						//如果有的话,就入队,准备进行再一次的BFS
						if(nx >=1 && nx <= N && ny >= 1 && ny <= M &&//判断是否出界
						 book[nx][ny] == 0 && E[nx][ny] == 'W')//判断是否是水,且没有走过
						{
							//先标记为走过,然后把它变成高早出,再入队
							book[nx][ny] = 1;
							E[nx][ny] = '.';
							
							//用临时pair变量temp来储存坐标
							temp.first = nx;
							temp.second = ny;
							que.push(temp);
						}
					}
					
				}
			}
		}
	}
	
	/*八连通的水'W' 会在一个while里全部变成干燥处'.',
	也就是说,外面两层for循环能够遍历到的水'W'的个数,就是水洼的个数*/
	cout << cnt;
	
	return 0;
}