信息学奥赛一本通（1249：Lake Counting）

1249：Lake Counting

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 9435     通过数: 4902

【题目描述】

题意：有一块N×M的土地，雨后积起了水，有水标记为‘W’，干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼？

【输入】

第一行为N,M(1≤N,M≤110)。

下面为N*M的土地示意图。

【输出】

一行，共有的水洼数。

【输入样例】

10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.

【输出样例】

3

【分析】

        这道题同细胞题目，属于图连通性问题，遍历地图，判断如果该点是水——'W'，则将该点改为陆地——'.' ，表示不返回。可以用深搜实现，也可以用广搜实现，深搜代码如下：

【参考代码1】

#include<stdio.h> #include <string.h>char a[1001][1001]; int n,m; void dfs(int x,int y) {int i,j,b,c;for(i=-1;i<2;i++) // 遍历九宫格 {for(j=-1;j<2;j++){ //(x,y)原点,b=x+i; //(x-1,y-1)左上、(x-1,y)上、(x-1,y+1)右上、(x,y-1)左、 c=y+j; //(x,y+1)右、(x+1,y-1)左下、(x+1,y)下、(x+1,y+1)右下 if(i==0 && j==0)continue; // 原点 if(b>=0 && b<n && y>=0 && y<m && a[b][c]=='W') // 边界判断和水判断 {a[b][c]='.'; // 如果该点是'W'，就改点为'.'，以后也不访问它 dfs(b,c); // 去搜索该点}}} } int main() {int i,j,num=0;scanf("%d %d",&n,&m);memset(a,'0',sizeof(a));for(i=0;i<=n-1;i++)scanf("%s",a[i]);for(i=0;i<n;i++){for(j=0;j<m;j++){if(a[i][j]=='W'){num++;//遇见一个水洼 就加加dfs(i,j);//去搜索这一点的八个方向}}}printf("%d\n",num);return 0; }

【参考代码2】

广搜C++代码如下：

#include <iostream> #include <cstdio> #include <queue>using namespace std; struct node {int x;int y; }; const int N=200;int n,m; char mapp[N][N]; //地图数组 int vis[N][N]; //访问数组 int dir[][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1}}; //方向数组 int sum;void bfs(int x,int y) {queue <node> q;node st;//标记起点st.x = x;st.y = y;mapp[x][y]='.';vis[x][y]=1;q.push(st);while(!q.empty()){node a=q.front();for(int i=0;i<8;i++) // 沿8个方向扩展 {node nw;nw.x = a.x + dir[i][0];nw.y = a.y + dir[i][1];if(nw.x >=0 && nw.x<n && nw.y>=0 && nw.y<m && (mapp[nw.x][nw.y]=='W')){mapp[nw.x][nw.y]='.';q.push(nw);}}q.pop();} } int main() {scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%s",mapp[i]);for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(mapp[i][j]=='W'){sum++;bfs(i,j);}}}printf("%d\n",sum);return 0; }

【参考代码3】

广搜C代码如下：

#include<stdio.h> #define N 100010 struct node {int x;int y; }q[N];int n,m; char a[120][120]; int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,1},{1,1},{1,-1},{-1,-1}};void bfs(int x0,int y0) {int i,head=1,tail=1;int x,y;int nx,ny;a[x0][y0]='.';q[tail].x=x0;q[tail].y=y0;tail++;while(head<tail){x=q[head].x;y=q[head].y;for(i=0;i<8;i++){nx=x+dir[i][0];ny=y+dir[i][1];if(nx>=0 && nx<n && ny>=0 && ny<m && a[nx][ny]=='W'){a[nx][ny]='.';q[tail].x=nx;q[tail].y=ny;tail++;}}head++;} } int main() {int i,j,sum=0;scanf("%d%d",&n,&m);for(i=0;i<n;i++)scanf("%s",a[i]);for(i=0;i<n;i++)for(j=0;j<m;j++)if(a[i][j]=='W'){sum++;bfs(i,j);}printf("%d\n",sum);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1249

总结

以上是生活随笔为你收集整理的信息学奥赛一本通（1249：Lake Counting）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。