题目链接 给你一个地图,'#'代表水,'.'代表陆地,'?'代表擦去的地图,可能是'#'也可能是'.'。地图中本该只有一块相连的陆地,若只有一种方案则输出确定的地图。若有多种方案,则输出‘Ambiguous’,若无答案,则输出‘Impossible’。
将所有‘.’进行dfs扫一遍,dfs时遇到的‘?’当作'.',因为被'#'包围的'?'一定代表‘#’。 一边记录相连的陆地数量b,一边记录当前相连陆地的总格数s0。 如果b==1,就对每个遇到过的'?',将其置为'#‘,再dfs一遍,如果扫到总格数小于s0-1,则有多种答案,否则就是一种答案。 如果b>1,则是无答案。
#include <bits/stdc++.h>
#define N 55
int n, m, a[N][N], u[N][N], x, y, b, s0, s, ok, fx[4] = {0, 0, 1, -1}, fy[4] = {1, -1, 0, 0};
char c;
void dfs(int x, int y)
{
if (u[x][y]) return;
u[x][y] = 1;
s++;
if (a[x][y] == 2) a[x][y] = 3;
for (int i = 0; i < 4; i++)
{
int nx = x + fx[i];
int ny = y + fy[i];
if (a[nx][ny])
dfs(nx, ny);
}
}
int main()
{
scanf("%d%d ", & n, & m);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
c = getchar();
if (c == '.') a[i][j] = 1;
else if (c == '?') a[i][j] = 2;
}
getchar();
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i][j] == 1 && !u[i][j])
{
b++;
dfs(i, j);
x = i;
y = j;
}
if(b == 1)
{
s0 = s;
for (int i = 1; i <= n && !ok; i++)
for (int j = 1; j <= m && !ok; j++)
if (a[i][j] == 3 )
{
memset(u, 0, sizeof u);
s = a[i][j] = 0;//? => #
dfs(x, y);
if(s == s0 - 1 )
ok = 1;
a[i][j] = 1;
}
if (ok)
printf("Ambiguous");
else
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
if (a[i][j] == 1) printf(".");
else printf("#");
printf("\n");
}
}
else printf("Impossible");
return 0;
}