1249：Lake Counting

Lake Counting"/>

1249：Lake Counting

【算法分析】

这道题的思路基本上和1329 细胞那道题一样。

四连通为：两个方块只有上下左右相邻才算连通。
八连通为：两方块之间可以是上下左右相邻，也可以是斜向相邻。比如一个方块在另一个方块的左上方、右下方、右上方、左下方。
该题中连通的概念为八连通。
只需要在原本的求连通块的代码中，将方向数组从上下左右4个位置，增加到上、下、左、右、左上、右上、左下、右下八个位置即可。
每次在搜索一个位置后，继续搜索该位置周围的八个位置，如果该位置在地图内、没访问过、且地图中该位置为’W’，那么访问该位置，接下来继续搜索该位置周围的八个位置。
统计连通块个数的解法为：遍历地图中的每个位置，尝试从每个位置开始进行搜索，一次成功开始的搜索意味着搜索到了一个连通块。统计成功开始搜索的次数，即为连通块的个数，也就是本题中的水洼数。
 

【代码】

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int x[8]={-1,-1,-1,0,1,1,1,0};
int y[8]={-1,0,1,1,1,0,-1,-1};
int n,m,td[112][112],que[1100][4];
int tj=0;
void bfs(int a,int b){tj++;int x1,y1,to=0,w=1;memset(que,0,sizeof(que));que[1][1]=a,que[1][2]=b,que[1][3]=0;td[a][b]=0;do{to++;for(int k=0;k<8;k++){x1=que[to][1]+x[k];y1=que[to][2]+y[k];if(x1>0&&x1<=n&&y1>0&&y1<=m&&td[x1][y1]==1){w++;que[w][1]=x1;que[w][2]=y1;que[w][3]=que[to][3]+1;td[x1][y1]=0;}}}while(w>to);
}
int main()
{scanf("%d %d",&n,&m);char t;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>t;if(t=='W')td[i][j]=1;else td[i][j]=0;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(td[i][j]==1) bfs(i,j);}printf("%d\n",tj);return 0;
}