描述

給你一張某一海域衛星照片，你需要統計：1. 照片中海島的數目2. 照片中面積不同的海島數目3. 照片中形狀不同的海島數目其中海域的照片如下，"."表示海洋，"#"表示陸地。在"上下左右"四個方向上連在一起的一片陸地組成一座島嶼。.####.. .....#. ####.#. .....#. ..##.#. 上圖所示的照片中一共有4座島嶼；其中3座面積為4，一座面積為2，所以不同面積的島嶼數目是2；有兩座形狀都是"####"，所以形狀不同的島嶼數目為3。

輸入

第一行包含兩個整數：N 和 M，(1 ≤ N, M ≤ 50)，表示照片的行數和列數。 以下一個 N * M 的矩陣，表示表示海域的照片。

輸出

輸出3個整數，依次是照片中海島的數目、面積不同的海島數目和形狀不同的海島數目。

樣例輸入

5 7 .####.. .....#. ####.#. .....#. ..##.#.

樣例輸出

4 2 3

解題思路

第一個結果和第二個結果很好處理，關鍵在于第三個如何標記島嶼的形狀。由于范圍比較小，開始便想著每一個島嶼都存在一個50*50的數組中，每次遍歷所有的島嶼數組判斷是否出現過，為了便于比較，在存放時每個點的位置減去起始點的位置。這樣過了40分……
后來發現

5 4 ..#. .### .... ..#. ..##

像這樣的一組數據是不能得出正確結果的，第一個島嶼起始點位置是（0，2），第二行第一列的位置是（1，1），相減得（1，-1），很明顯不對。
最終改成一維數組來存放數組的形狀，事先將地圖從左上到右下依次編號，在數組中存放編號即可（為了便于比較，每個位置應減去起始點的編號值）。

代碼實現

#include <iostream> #include <cstdio> #include<cstring> #include<queue> using namespace std; #define maxn 6 bool varea[maxn]; //標記面積值是否出現過 char maps[maxn][maxn],str[maxn]; int a[maxn][maxn*maxn],visit[maxn][maxn]; int m,n,area,countt; int dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}}; queue<pair<int,int> >qu; void bfs(int x,int y) {int cha=x*n+y;qu.push(make_pair(x,y));while(!qu.empty()){int xx=qu.front().first;int yy=qu.front().second;a[countt][area]=(xx*n+yy)-cha; //存放島嶼形狀area++;qu.pop();for(int i=0; i<4; i++){int nx=xx+dir[i][0];int ny=yy+dir[i][1];if(nx>=0&&nx<m&&ny>=0&&ny<n&&maps[nx][ny]=='#'&&!visit[nx][ny]){qu.push(make_pair(nx,ny));visit[nx][ny]=1;}}} } int main() {int ans,ansarea,ansdif; //分別代表三個結果值bool flag;while(~scanf("%d %d%*c",&m,&n)){ans=0;ansarea=0;ansdif=0;countt=-1;memset(varea,0,sizeof(varea));memset(a,0,sizeof(a));memset(visit,0,sizeof(visit));for(int i=0; i<m; i++){scanf("%s",str);for(int j=0; j<n; j++)maps[i][j]=str[j];}for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(!visit[i][j]&&maps[i][j]=='#'){visit[i][j]=1;countt++;if(countt==0) ansdif++;area=0;bfs(i,j);if(!varea[area]){ansarea++;varea[area]=1;}flag=true;for(int k=0; k<countt; k++){flag=true;for(int p=0; p<maxn*maxn-1; p++){if(a[countt][p]!=a[k][p]){flag=false;break;}}if(flag) break;}if(!flag) ansdif++;ans++;}}}printf("%d %d %d\n",ans,ansarea,ansdif);}return 0; }

PS:

由于內存分配的原理，數組（1，-1）的地址會是上一行的最末尾位置的地址，那么原來的方法的也可以通過啦，貼在這里警示自己以后不可以再考慮不到這樣易錯的情況。

#include <iostream> #include <cstdio> #include<cstring> #include<queue> using namespace std; #define maxn 54 bool varea[maxn*maxn]; char maps[maxn][maxn],str[maxn]; int a[1500][100][100],visit[maxn][maxn]; int m,n,area,countt; int dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}}; queue<pair<int,int> >qu; void bfs(int x,int y) {qu.push(make_pair(x,y));while(!qu.empty()){int xx=qu.front().first;int yy=qu.front().second;a[countt][xx-x][yy-y]=1;qu.pop();for(int i=0; i<4; i++){int nx=xx+dir[i][0];int ny=yy+dir[i][1];if(nx>=0&&nx<m&&ny>=0&&ny<n&&maps[nx][ny]=='#'&&!visit[nx][ny]){area++;qu.push(make_pair(nx,ny));visit[nx][ny]=1;}}} } int main() {int ans,ansarea,ansdif;bool flag;while(~scanf("%d %d%*c",&m,&n)){ans=0;ansarea=0;ansdif=0;countt=-1;memset(varea,0,sizeof(varea));memset(a,0,sizeof(a));memset(visit,0,sizeof(visit));for(int i=0; i<m; i++){scanf("%s",str);for(int j=0; j<n; j++){maps[i][j]=str[j];}}for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(!visit[i][j]&&maps[i][j]=='#'){countt++;if(countt==0) ansdif++;area=0;bfs(i,j);if(!varea[area]){ansarea++;varea[area]=1;}flag=true;for(int k=0; k<countt; k++){flag=true;for(int p=0; p<100; p++){for(int q=0; q<100; q++){if(a[countt][p][q]!=a[k][p][q]){flag=false;break;}}if(!flag)break;}if(flag) break;}if(!flag)ansdif++;ans++;}}}printf("%d %d %d\n",ans,ansarea,ansdif);}return 0; }

總結

以上是生活随笔為你收集整理的hihoCoder 156周 岛屿的全部內容，希望文章能夠幫你解決所遇到的問題。

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