用c++语言帮助我编写一个程序,要求第一行输入两个整数m和n,接下来输入m行n列的网格,其中#表示墙壁,.表示空格,从任意空格出发,输出能够到达的空格数。
时间: 2024-10-02 11:02:57 浏览: 16
当然可以。这是一个基本的迷宫遍历问题,我们可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法来解决。这里我将提供一个简单的深度优先搜索解决方案,因为它的代码更简洁一些。
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 布局结构,代表网格中的每个位置
struct Position {
int row;
int col;
};
// 检查当前位置是否有效(在范围内且不是墙壁)
bool isValid(int m, int n, Position pos) {
return pos.row >= 0 && pos.row < m && pos.col >= 0 && pos.col < n && grid[pos.row][pos.col] == '.';
}
// DFS遍历并递归标记已访问过的节点
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int m, int n, Position start) {
visited[start.row][start.col] = true;
cout << 1 << " "; // 记录可达空格数
if (isValid(m, n, {start.row + 1, start.col})) {
dfs(grid, visited, m, n, {start.row + 1, start.col});
}
if (isValid(m, n, {start.row - 1, start.col})) {
dfs(grid, visited, m, n, {start.row - 1, start.col});
}
if (isValid(m, n, {start.row, start.col + 1})) {
dfs(grid, visited, m, n, {start.row, start.col + 1});
}
if (isValid(m, n, {start.row, start.col - 1})) {
dfs(grid, visited, m, n, {start.row, start.col - 1});
}
}
int main() {
int m, n;
cout << "请输入矩阵的行数m和列数n: ";
cin >> m >> n;
// 初始化网格和访问标记矩阵
vector<vector<char>> grid(m, vector<char>(n));
vector<vector<bool>> visited(m, vector<bool>(n, false));
// 读取输入的网格
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cin >> grid[i][j];
}
}
// 从第一个空格开始搜索
Position start;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '.') {
start.row = i;
start.col = j;
break;
}
}
if (start.row != -1) {
break;
}
}
dfs(grid, visited, m, n, start);
// 结束搜索后输出可达空格总数
cout << endl << "总共有" << visited.size() << "个可达空格。\n";
return 0;
}
```
阅读全文