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.
62 lines
1.1 KiB
62 lines
1.1 KiB
/*着色法:在深度优化搜索里增加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("%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);//用-1表示对齐进行染色
|
|
|
|
//输出已经染色后的地图
|
|
for (i = 1; i <= n; i++) {
|
|
for (j = 1; j <= m; j++) {
|
|
printf("%3d", a[i][j]);//%3d中的3是c语言中的场宽
|
|
}
|
|
printf("\n");
|
|
}
|
|
getchar();
|
|
getchar();
|
|
return 0;
|
|
}
|