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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。