c++代码(请用bfs来写) 在一个N*N的迷宫里,计算从一个起始点(x,y)开始移动能到达的格子数。移动的法则是每一步可以上,下,顶-左,底-右。 输入格式: 三个整数N,x和y,代表迷宫的大小和起始点位置。 下面N行:每一行是用空格分开的N个0或1。0代表了可以填进去的格子,1代表了障碍。 输出格式: 能够到达的格子数。 样例输入: 3 0 0 0 0 0 0 1 0 1 0 1 样例输出: 3
时间: 2024-04-17 08:24:29 浏览: 69
以下是使用BFS算法来解决这个问题的C++代码:
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int bfs(vector<vector<int>>& maze, int start_x, int start_y) {
int n = maze.size();
int count = 0;
vector<vector<bool>> visited(n, vector<bool>(n, false));
queue<pair<int, int>> q;
// 初始位置入队列
q.push(make_pair(start_x, start_y));
visited[start_x][start_y] = true;
count++;
// 定义上、下、左、右四个方向的偏移量
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
while (!q.empty()) {
pair<int, int> curr = q.front();
q.pop();
// 遍历四个方向
for (int i = 0; i < 4; i++) {
int new_x = curr.first + dx[i];
int new_y = curr.second + dy[i];
// 判断新位置是否在迷宫范围内,并且是可以填进去的格子
if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < n && maze[new_x][new_y] == 0 && !visited[new_x][new_y]) {
q.push(make_pair(new_x, new_y));
visited[new_x][new_y] = true;
count++;
}
}
}
return count;
}
int main() {
int N, x, y;
cin >> N >> x >> y;
vector<vector<int>> maze(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> maze[i][j];
}
}
int result = bfs(maze, x, y);
cout << result << endl;
return 0;
}
```
你可以将上述代码保存为一个.cpp文件,然后使用C++编译器进行编译和运行。输入迷宫的大小和起始点位置,以及迷宫矩阵,然后输出能够到达的格子数。
阅读全文