【题目链接】
ybt 1249：Lake Counting
OpenJudge NOI 2.5 1388:Lake Counting
【题目考点】
1. 搜索 连通块问题
【解题思路】
四连通为：两个方块只有上下左右相邻才算连通。
八连通为：两方块之间可以是上下左右相邻，也可以是斜向相邻。比如一个方块在另一个方块的左上方、右下方、右上方、左下方。
该题中连通的概念为八连通。
只需要在原本的求连通块的代码中，将方向数组从上下左右4个位置，增加到上、下、左、右、左上、右上、左下、右下八个位置即可。
每次在搜索一个位置后，继续搜索该位置周围的八个位置，如果该位置在地图内、没访问过、且地图中该位置为’W’，那么访问该位置，接下来继续搜索该位置周围的八个位置。
统计连通块个数的解法为：遍历地图中的每个位置，尝试从每个位置开始进行搜索，一次成功开始的搜索意味着搜索到了一个连通块。统计成功开始搜索的次数，即为连通块的个数，也就是本题中的水洼数。
连通块问题可以用深搜或广搜来解决。
【题解代码】
解法1：深搜
#include <bits/stdc++.h>
using namespace std;
#define N 120
int n, m, ct;//ct：连通块个数
char mp[N][N];//地图
bool vis[N][N];//vis[i][j]：第(i,j)位置是否已访问
int dir[8][2] = {{-1,0},{1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};//八连通方向数组，一个位置周围八个位置的坐标与中心位置的差值。
void dfs(int sx, int sy)//从(sx,sy)开始进行深搜
{
for(int i = 0; i < 8; ++i)
{
int x = sx + dir[i][0], y = sy + dir[i][1];//新位置(x,y)
if(x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y] == false && mp[x][y] == 'W')
{//如果(x,y)在地图内，没访问过 ，且该位置是'W'
vis[x][y] = true;
dfs(x, y);
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
cin >> mp[i][j];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
if(mp[i][j] == 'W' && vis[i][j] == false)//如果该位置是'W'且没访问过
{
vis[i][j] = true;
dfs(i, j);//从这里开始进行一次深搜
ct++;//找到了一个连通块
}
}
cout << ct;//输出连通块的个数
return 0;
}
解法2：广搜
#include <bits/stdc++.h>
using namespace std;
#define N 120
struct Node
{
int x, y;
Node(){}
Node(int a, int b):x(a),y(b){}
};
int n, m, ct;//ct：连通块个数
char mp[N][N];//地图
bool vis[N][N];//vis[i][j]：第(i,j)位置是否已访问
int dir[8][2] = {{-1,0},{1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};//八连通方向数组，一个位置周围八个位置的坐标与中心位置的差值。
void bfs(int stx, int sty)//从(stx,sty)开始进行广搜
{
queue<Node> que;
que.push(Node(stx, sty));
vis[stx][sty] = true;
while(que.empty() == false)
{
Node sel = que.front();
que.pop();
for(int i = 0; i < 8; ++i)
{
int x = sel.x + dir[i][0], y = sel.y + dir[i][1];//新位置(x,y)
if(x >= 1 && x <= n && y >= 1 && y <= m && vis[x][y] == false && mp[x][y] == 'W')
{//如果(x,y)在地图内，没访问过 ，且该位置是'W'
vis[x][y] = true;
que.push(Node(x, y));
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
cin >> mp[i][j];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
if(mp[i][j] == 'W' && vis[i][j] == false)//如果该位置是'W'且没访问过
{
bfs(i, j);//从这里开始进行一次广搜
ct++;//找到了一个连通块
}
}
cout << ct;//输出连通块的个数
return 0;
}
