在一个 w×h 的矩形广场上,每一块 1×1 的地面都铺设了红色或黑色的瓷砖。小林同学站在某一块黑色的瓷砖上,他可以从此处出发,移动到上、下、左、右四个相邻的且是黑色的瓷砖上。现在,他想知道,通过重复上述移动所能经过的黑色瓷砖数。c++
时间: 2024-04-17 19:25:45 浏览: 254
下面是一个用C++实现广度优先搜索(BFS)算法来解决该问题的代码示例:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 定义坐标结构体
struct Coordinate {
int x;
int y;
Coordinate(int _x, int _y) : x(_x), y(_y) {}
};
// 检查坐标是否在矩形范围内
bool isValid(int x, int y, int w, int h) {
return x >= 0 && x < w && y >= 0 && y < h;
}
int bfs(vector<vector<char>>& grid, Coordinate start) {
int w = grid.size();
int h = grid[0].size();
vector<vector<bool>> visited(w, vector<bool>(h, false)); // 记录已访问的瓷砖
int count = 0; // 经过的黑色瓷砖数
queue<Coordinate> q; // 定义广度优先搜索队列
q.push(start);
while (!q.empty()) {
Coordinate tile = q.front();
q.pop();
if (!visited[tile.x][tile.y]) {
visited[tile.x][tile.y] = true;
count++;
// 检查四个相邻瓷砖
vector<Coordinate> neighbors = {{tile.x - 1, tile.y}, {tile.x + 1, tile.y}, {tile.x, tile.y - 1}, {tile.x, tile.y + 1}};
for (const auto& neighbor : neighbors) {
int nx = neighbor.x;
int ny = neighbor.y;
if (isValid(nx, ny, w, h) && grid[nx][ny] == 'B' && !visited[nx][ny]) {
q.push(neighbor);
}
}
}
}
return count;
}
int main() {
int w, h;
cin >> w >> h;
vector<vector<char>> grid(w, vector<char>(h));
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
cin >> grid[i][j];
}
}
int start_x, start_y;
cin >> start_x >> start_y;
Coordinate start(start_x, start_y);
int black_tiles_count = bfs(grid, start);
cout << black_tiles_count << endl;
return 0;
}
```
在这个示例中,我们首先输入了矩形广场的宽度w和高度h,然后输入了每个瓷砖的颜色('R'代表红色,'B'代表黑色)。接下来,我们输入了小林同学所站的黑色瓷砖的坐标。最后输出通过重复移动能够经过的黑色瓷砖数量。
希望这个示例能够帮助你理解如何用C++实现广度优先搜索算法解决该问题。如果有任何疑问,请随时提问。
阅读全文