在一个n*m二维网格图中,有以下三种地形:“﹟”代表湖泊;“.”代表陆地;?代表陆地与湖泊有可能的未知地形,求是否存在一种或多种在未知地形填充湖泊/陆地的方案,使得最后地上全部的陆地区域组成一个四联通块(陆地四联通是指,在任意一个陆地格子出发,只是任意使用上下左右四个方向操作,可以访问到任何一块其他的陆地)。 无解输出“Impossible”,多解输出“Ambiguous”,唯一解输出一个n*m的网格图,使得之前的“?”均被填充为“﹟”或“.”,且陆地四联通。 Input format :第一行两个整数n,m代表地形的行、列数。后面一个n行m列的矩阵代表地形。 Output format:如题意(不含引号)。 Sample Input1 5 7 C++实现
时间: 2024-02-25 15:58:02 浏览: 17
很高兴为您解答这个问题。这是一个比较复杂的问题,需要一些算法知识来解决。以下是一个使用 BFS 和 DFS 算法的 C++ 实现。
```c++
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 50 + 5;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int n, m, cnt, ans;
int g[MAXN][MAXN], vis[MAXN][MAXN], color[MAXN][MAXN];
bool ambiguous;
queue<pair<int, int>> q;
void bfs(int x, int y, int c) {
q.push(make_pair(x, y));
vis[x][y] = cnt;
color[x][y] = c;
while (!q.empty()) {
auto u = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nx = u.first + dx[i];
int ny = u.second + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
if (g[nx][ny] == 1 && vis[nx][ny] != cnt) {
vis[nx][ny] = cnt;
color[nx][ny] = c;
q.push(make_pair(nx, ny));
}
}
}
}
}
void dfs(int x, int y, int c) {
if (x < 0 || x >= n || y < 0 || y >= m) {
return;
}
if (g[x][y] == 0 || vis[x][y] == cnt) {
return;
}
if (color[x][y] != c) {
ambiguous = true;
return;
}
vis[x][y] = cnt;
for (int i = 0; i < 4; i++) {
dfs(x + dx[i], y + dy[i], c);
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
cin >> c;
if (c == '#') {
g[i][j] = 1;
} else if (c == '.') {
g[i][j] = 2;
} else {
g[i][j] = 3;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 1 && vis[i][j] == 0) {
cnt++;
bfs(i, j, cnt % 2 + 1);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 2 && vis[i][j] == 0) {
cnt++;
dfs(i, j, color[i][j]);
if (ambiguous) {
cout << "Impossible" << endl;
return 0;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 3) {
cout << ".";
} else if (color[i][j] == 1) {
cout << "#";
} else {
cout << ".";
}
}
cout << endl;
}
return 0;
}
```
算法思路:
首先,我们将所有已知的湖泊和陆地分别标记为1和2,未知地形标记为3。接下来,我们用 BFS 算法遍历所有的湖泊,并将它们标记为 A 类或 B 类。具体方法是,如果当前湖泊尚未被遍历过,则将它们全部加入队列中,并标记为当前计数器的值。然后,我们从队列中取出每一个湖泊,遍历它的四个相邻格子,如果相邻格子是陆地且尚未被遍历过,则将其标记为与当前湖泊相反的类型,加入队列中,并标记为已遍历过。
接下来,我们用 DFS 算法遍历所有的未知地形,并判断其是否与相邻的陆地为同一种类型。具体方法是,从任意一块未知地形出发,遍历所有相邻的陆地,将它们标记为已遍历过,如果相邻的陆地与当前未知地形的类型不同,则存在多解。如果遍历完成后仍未出现多解,则说明存在唯一解。
最后,我们将所有的未知地形填充为陆地或湖泊,具体方法是,如果某一块格子是未知地形,则根据其相邻的湖泊的类型将其填充为湖泊或陆地。
希望我的回答能够帮助到您!