/*着色法:在深度优化搜索里增加color的参数*/ #include<stdio.h> int a[51][51]; int book[51][51]; int n, m, sum; void dfs(int x, int y, int color) { int k, tx, ty; //定义一个方向数组 int next[4][2] = { { 0, 1 },//向右走 { 1, 0 },//向下走 { 0, -1 },//向左走 { -1, 0 } };//向上走 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);//开始尝试下一个点 } } return; } int main() { int i, j, startx, starty; scanf_s("%d %d %d %d", &n, &m, &startx, &starty); //读入地图 for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) scanf_s("%d", &a[i][j]); //读入地图 book[startx][starty] = 1; sum = 1; dfs(startx, starty, -1);//用-1表示对齐进行染色 //输出已经染色后的地图 for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { printf("%3d", a[i][j]);//%3d中的3是c语言中的场宽 } printf(" "); } getchar(); getchar(); return 0; }
如果想知道一副地图里有多少个独立的小岛又该怎么做呢？
so easy。只需要对地图上的每一个大于0的点都进行一遍深度优先搜索即可，因为等于0的点是海洋，小于0的点是已经被染色的小岛。
可以从（1，1）开始，一直枚举到（n，m），对每个点进行尝试染色。
/*着色法:在深度优化搜索里增加color的参数*/ #include<stdio.h> int a[51][51]; int book[51][51]; int n, m, sum; void dfs(int x, int y, int color) { int k, tx, ty; //定义一个方向数组 int next[4][2] = { { 0, 1 },//向右走 { 1, 0 },//向下走 { 0, -1 },//向左走 { -1, 0 } };//向上走 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);//开始尝试下一个点 } } return; } int main() { int i, j, num = 0; scanf_s("%d %d", &n, &m); //读入地图 for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) scanf_s("%d", &a[i][j]); //读入地图 //对每一个大于0的点尝试进行dfs染色 for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { if (a[i][j] > 0) { num--;//小岛需要染色的颜色编号 //每发现一个小岛应染以不同的颜色，因此每次要-1 book[i][j] = 1; dfs(i, j, num);//对不同小岛按照num进行染色 } } } //输出已经染色后的地图 for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { printf("%3d", a[i][j]);//%3d中的3是c语言中的场宽 } printf(" "); } //输出小岛的个数 printf("有%d个小岛 ", -num); getchar(); getchar(); return 0; }
