宽搜：
测试数据：
10 10 6 8
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0
代码：
#include <stdio.h> struct node{ int x; int y; }; int main() { struct node que[2501]; int a[51][51]; int book[51][51] = {0}; int next[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; int n,m,startx,starty,head,tail,i,j,sum,tx,ty; //输入地图大小，起始点 scanf("%d%d%d%d",&n,&m,&startx,&starty); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&a[i][j]); head=1,tail=1; que[tail].x = startx; que[tail].y = starty; tail++; book[startx][starty] = 1; sum=1; while(head<tail) { for(i=0;i<4;i++) { //求出下一个方向的点 tx = que[head].x+next[i][0]; ty = que[head].y+next[i][1]; if(tx<1||tx>n||ty<1||ty>m) continue; if(a[tx][ty]>0&&book[tx][ty]==0){ book[tx][ty] = 1; que[tail].x = tx; que[tail].y = ty; tail++; sum++; } } head++; } printf("%d",sum); return 0; }
运行结果：38
——————————————————————————————————————
深搜：
可以将地图对应位置改成-1，又叫染色法
#include <stdio.h> int a[51][51]; int book[51][51]={0},n,m,sum; void dfs(int x,int y,int color) { //定义四个方向 int next[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; int i,tx,ty; a[x][y]=color; //列举四个方向 for(i=0;i<4;i++){ tx = x+next[i][0]; ty = y+next[i][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); } } return; } int main() { int i,j,startx,starty; scanf("%d%d%d%d",&n,&m,&startx,&starty); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&a[i][j]); book[startx][starty]=1; sum=1; //从降落的地方开始 dfs(startx,starty,-1); printf("%d\n",sum); for(i=1;i<=n;i++){ for(j=1;j<=m;j++) printf("%3d",a[i][j]); printf("\n"); } return 0; }
运行结果：
——————————————————————————————————————
3.若想求出整张地图有几个岛屿，用深搜怎么来求
输入条件：
10 10
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0
代码：
#include <stdio.h> int a[51][51]; int book[51][51]={0}; int n,m,sum; void dfs(int x,int y,int color) { int next[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; a[x][y] = color; int i,j,tx,ty; for(i=0;i<4;i++){ tx = x+next[i][0]; ty = y+next[i][1]; if(tx<1||tx>n||ty<1||ty>m) continue; if(a[tx][ty]>0&&book[tx][ty]==0){ book[tx][ty]=1; dfs(tx,ty,color); } } return; } int main() { int i,j,num=0; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&a[i][j]); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(a[i][j]>0){ num--; 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]); printf("\n"); } printf("找到%d个岛屿",-num); return 0; }
运行结果：
