用c++实现:在一个n*m二维网格图中,有以下三种地形:'#'代表湖泊;'.'代表陆地;'?'代表陆地与湖泊均有可能的未知地形。 求是否存在一种或多种在未知地形填充湖泊/陆地的方案,使得最后地上全部的陆地区域组成一个四联通的联通块
时间: 2024-02-15 20:01:46 浏览: 64
四连通种子填充算法C++实现
4星 · 用户满意度95%
这道题可以使用深度优先搜索(DFS)来解决。首先,我们需要将所有已知的湖泊标记出来,然后从一个陆地区域开始进行 DFS,递归地搜索相邻的陆地区域,并将它们标记为已访问。
在搜索过程中,我们需要判断当前搜索到的区域是否是湖泊,如果是湖泊则不能继续向相邻的陆地区域进行搜索。如果在搜索结束后,所有的陆地区域都被标记为已访问,则说明存在一种或多种方案可以填充湖泊/陆地,使得最后地上全部的陆地区域组成一个四联通的联通块,反之则不存在。
下面是 C++ 的代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<vector<char>> grid;
vector<vector<bool>> visited;
int n, m;
void dfs(int i, int j) {
if (i < 0 || i >= n || j < 0 || j >= m || visited[i][j] || grid[i][j] == '#') {
return;
}
visited[i][j] = true;
dfs(i-1, j);
dfs(i+1, j);
dfs(i, j-1);
dfs(i, j+1);
}
bool is_possible() {
visited.assign(n, vector<bool>(m, false));
bool found_land = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '#') {
visited[i][j] = true;
} else if (grid[i][j] == '.' && !found_land) {
dfs(i, j);
found_land = true;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '.' && !visited[i][j]) {
return false;
}
}
}
return true;
}
int main() {
cin >> n >> m;
grid.assign(n, vector<char>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
if (is_possible()) {
cout << "Possible" << endl;
} else {
cout << "Impossible" << endl;
}
return 0;
}
```
输入格式为先输入 n 和 m,表示网格图的行数和列数,接下来输入 n 行,每行 m 个字符,表示网格图的地形。输出 "Possible" 表示存在一种或多种方案可以填充湖泊/陆地,使得最后地上全部的陆地区域组成一个四联通的联通块,输出 "Impossible" 表示不存在这样的方案。
阅读全文