请用c++实现:在一个n*m二维网格图中,有以下三种地形:'#'代表湖泊;'.'代表陆地;'?'代表陆地与湖泊均有可能的未知地形。 求是否存在一种或多种在未知地形填充湖泊/陆地的方案,使得最后地上全部的陆地区域组成一个四联通的联通块(陆地四联通是指,在任意一个陆地格子出发,只是任意使用上下左右四个方向操作,可以访问到任何一块其他的陆地)。 无解输出“Impossible”,多解输出“Ambiguous”,唯一解则须输出一个n*m的网格图,使得之前的“?”均被填充为“#”或“.”,且陆地四联通。
时间: 2024-02-12 20:07:16 浏览: 74
以下是使用C++实现的代码,使用BFS算法进行搜索:
```c++
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1005;
char map[MAXN][MAXN];
bool vis[MAXN][MAXN];
int n, m, cnt, sx, sy;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool bfs(int x, int y, char c) {
queue<pair<int, int>> q;
q.push(make_pair(x, y));
vis[x][y] = true;
while (!q.empty()) {
int fx = q.front().first, fy = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = fx + dx[i], ny = fy + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (map[nx][ny] != c) continue;
if (vis[nx][ny]) continue;
vis[nx][ny] = true;
q.push(make_pair(nx, ny));
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (map[i][j] == c && !vis[i][j]) {
return false;
}
}
}
return true;
}
bool check(char c) {
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (map[i][j] == c) {
sx = i;
sy = j;
break;
}
}
}
return bfs(sx, sy, c);
}
bool solve() {
bool flag = false;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (map[i][j] == '.') {
cnt++;
if (cnt == 1) {
flag |= check('#');
if (!flag) return false;
}
map[i][j] = '#';
if (!check('.')) {
if (flag) return true;
else return false;
}
map[i][j] = '.';
cnt--;
flag = true;
} else if (map[i][j] == '#') {
cnt++;
if (cnt == 1) {
flag |= check('.');
if (!flag) return false;
}
map[i][j] = '.';
if (!check('#')) {
if (flag) return true;
else return false;
}
map[i][j] = '#';
cnt--;
flag = true;
}
}
}
return true;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> map[i][j];
if (map[i][j] == '.') cnt++;
}
}
if (!check('.') || !check('#')) {
cout << "Impossible" << endl;
return 0;
}
if (solve()) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << map[i][j];
}
cout << endl;
}
} else {
cout << "Ambiguous" << endl;
}
return 0;
}
```
其中,bfs函数用于检查从一个点出发是否能够到达另一个点,并且保证路径中的所有点都是同一种地形。check函数用于检查是否存在一块四联通的陆地,solve函数用于枚举所有未知地形的情况,判断是否存在唯一解或多解。
阅读全文