You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
74 lines
1.6 KiB
74 lines
1.6 KiB
#include<iostream>
|
|
using namespace std;
|
|
int main() {
|
|
struct mark {
|
|
int x;
|
|
int y;
|
|
};
|
|
//建立一个队列
|
|
struct mark que[2501];
|
|
int square=1;
|
|
//建立岛屿面积变量
|
|
int head,tail;
|
|
int n,m;
|
|
int p,q,k;
|
|
int book[51][51];
|
|
//使用book数组标记是否经过这个区域
|
|
int a[51][51];
|
|
int color=0;
|
|
//对每座岛屿进行染色，并统计岛屿的数量
|
|
head=1;
|
|
tail=1;
|
|
cout << "please input the map of row and col: ";
|
|
cin >> n >>m;
|
|
cout << "please input the map: "<<endl;
|
|
for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) cin >> a[i][j];
|
|
for(p=1; p<=n; ++p) {
|
|
for(q=1; q<=m; ++q) {
|
|
if(a[p][q]>0)
|
|
//若发现一个新岛屿
|
|
{
|
|
color--;
|
|
book[p][q]=1;
|
|
que[tail].x=p;
|
|
que[tail].y=q;
|
|
++tail;
|
|
while(head<tail)
|
|
//广度优先算法的核心
|
|
{
|
|
int next[4][2]= {{1,0},
|
|
//建立一个方向数组，实现对四个方向的枚举 {0,1}, {0,-1}, {-1,0}};
|
|
a[p][q]=color;
|
|
for(k=0; k<4; ++k) {
|
|
int tx=que[head].x+next[k][0];
|
|
int ty=que[head].y+next[k][1];
|
|
if((tx < 0) || (ty < 0) || (tx > n) || (ty > m))
|
|
//判断是否越界
|
|
continue;
|
|
if((a[tx][ty]>0) && (book[tx][ty] == 0))
|
|
//判断是否为陆地、是否已经标记过
|
|
{
|
|
book[tx][ty]=1;
|
|
++square;
|
|
a[tx][ty]=color;
|
|
que[tail].x=tx;
|
|
que[tail].y=ty;
|
|
++tail;
|
|
}
|
|
} ++head;
|
|
//这一步很关键，每一点扩展完毕后，该点就无效了，所以相当于出队列
|
|
}
|
|
}
|
|
}
|
|
}
|
|
for(int i=1; i<=n; ++i) {
|
|
for(int j=1; j<=m; ++j) {
|
|
cout << a[i][j] <<" ";
|
|
}
|
|
cout << endl;
|
|
}
|
|
cout << "the island of the square : " << square <<endl;
|
|
return 0;
|
|
}
|
|
|