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.
66 lines
1.3 KiB
66 lines
1.3 KiB
//啊哈算法114~116页代码
|
|
/*使用深度优先 求地图上的独立小岛数*/
|
|
#include <stdio.h>
|
|
int a[51][51];
|
|
int book[51][51],n,m,sum;
|
|
void dfs(int x,int y,int color) {
|
|
//定义一个方向数组 依次向右、向下、向左、向上（即顺时针）
|
|
int next[4][2]= {{0,1}, {1,0},{0,-1},{-1,0}};
|
|
int k,tx,ty;
|
|
|
|
a[x][y]=color;//对a[x][y]这个格子染色
|
|
//四个方向依次遍历
|
|
for(k=0; k<4; k++) {
|
|
tx=x+next[k][0];//要检查的下一坐标
|
|
ty=y+next[k][1];
|
|
//判断是否越界
|
|
if(tx<1||tx>n||ty<1||ty>m)
|
|
continue;
|
|
//判断是否为陆地及是否被标记
|
|
if(a[tx][ty]>0 && book[tx][ty]==0) {
|
|
sum++;
|
|
book[tx][ty]==1;
|
|
//标记该点已走过
|
|
dfs(tx,ty,color); //对该点着色 继续执行dfs()尝试下一点
|
|
}
|
|
}
|
|
return;
|
|
}
|
|
|
|
int main() {
|
|
int i,j,num=0;
|
|
scanf("%d %d %d",&n,&m);
|
|
//输入行列数 n m
|
|
|
|
//读入地图数据
|
|
for(i=1; i<=n; i++) {
|
|
for(j=1; j<=m; j++) {
|
|
scanf("%d",&a[i][j]);
|
|
}
|
|
}
|
|
|
|
//对每个大于0的点尝试进行dfs染色
|
|
for(i=1; i<=n; i++) {
|
|
for(j=1; j<=m; j++) {
|
|
if(a[i][j]>0) {
|
|
num--; //输出染色后的地图 for(i=1;i<=n;i++)
|
|
book[i][j] = 1;
|
|
dfs(i,j,num);
|
|
}
|
|
}
|
|
}
|
|
//输出已经染色后的地图
|
|
for(i=1; i<=n; i++) {
|
|
for(j=1; j<=m; j++) {
|
|
printf("%3d",a[i][j]);//3是C语言中的场宽
|
|
}
|
|
printf("\n");
|
|
}
|
|
//输出小岛的个数
|
|
printf("有%d个小岛\n",-num);
|
|
getchar();
|
|
getchar();
|
|
return 0;
|
|
}
|
|
|