在一个n*m二维网格图中,有以下三种地形:“﹟”代表湖泊;“.”代表陆地;?代表陆地与湖泊有可能的未知地形,求是否存在一种或多种在未知地形填充湖泊/陆地的方案,使得最后地上全部的陆地区域组成一个四联通块(陆地四联通是指,在任意一个陆地格子出发,只是任意使用上下左右四个方向操作,可以访问到任何一块其他的陆地)。 无解输出“Impossible”,多解输出“Ambiguous”,唯一解输出一个n*m的网格图,使得之前的“?”均被填充为“﹟”或“.”,且陆地四联通。 Input format :第一行两个整数n,m代表地形的行、列数。后面一个n行m列的矩阵代表地形。 Output format:如题意(不含引号)。C++
时间: 2024-02-25 13:57:50 浏览: 81
以下是一份C++的代码实现,使用了深度优先搜索(DFS)算法:
```c++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 105;
char grid[MAXN][MAXN];
int n, m;
bool vis[MAXN][MAXN];
bool check() { // 检查是否四联通
int cnt = 0;
int sx = -1, sy = -1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (grid[i][j] == '.') {
cnt++;
if (sx == -1 && sy == -1) {
sx = i;
sy = j;
}
}
}
}
if (cnt == 0) return true;
memset(vis, false, sizeof(vis));
vis[sx][sy] = true;
dfs(sx, sy);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (grid[i][j] == '.' && !vis[i][j]) {
return false;
}
}
}
return true;
}
void dfs(int x, int y) { // DFS遍历连通块
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && grid[nx][ny] == '.') {
vis[nx][ny] = true;
dfs(nx, ny);
}
}
}
bool dfs2(int x, int y) { // DFS枚举填充情况
if (x == n + 1) {
return check();
}
int nx = x, ny = y + 1;
if (ny > m) {
nx = x + 1;
ny = 1;
}
if (grid[x][y] != '?') {
return dfs2(nx, ny);
}
grid[x][y] = '#';
bool res1 = dfs2(nx, ny);
grid[x][y] = '.';
bool res2 = dfs2(nx, ny);
if (res1 && res2) {
cout << "Ambiguous" << endl;
exit(0);
} else if (res1) {
return true;
} else if (res2) {
return true;
} else {
grid[x][y] = '?';
return false;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> grid[i][j];
}
}
if (!dfs2(1, 1)) {
cout << "Impossible" << endl;
} else {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << grid[i][j];
}
cout << endl;
}
}
return 0;
}
```
代码实现中,`check()`函数用于检查是否满足四联通块的要求;`dfs()`函数用于深度优先搜索遍历连通块;`dfs2()`函数用于枚举填充情况,判断是否存在唯一解或多解,以及是否无解。
在`dfs2()`函数中,对于每个未知状态,我们分别进行填充湖泊和填充陆地两种尝试,然后递归判断是否满足四联通块要求。如果两种尝试均可以得到满足四联通块要求的结果,那么输出“Ambiguous”。如果只有一种尝试可以得到满足四联通块要求的结果,那么就填充这个状态,并递归到下一个状态。如果两种尝试均不能得到满足四联通块要求的结果,那么我们就将这个状态还原成未知状态,并返回false。
最后,如果无解,输出“Impossible”;如果有唯一解,输出这个解。
阅读全文