c++:给你一个 n x m 的矩阵 board ,由若干字符 'X' 和 'O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。(字符 'X' 和 'O' 均为大写字母)
时间: 2023-08-26 09:04:07 浏览: 53
你可以使用深度优先搜索(DFS)来解决这个问题。首先,遍历矩阵的边界,将边界上的 'O' 及与其相邻的 'O' 标记为特殊字符,比如 '#'; 然后再遍历整个矩阵,将剩余的 'O' 替换为 'X',同时将标记的特殊字符 '#' 恢复为 'O'。下面是一个示例的 C++ 实现:
```cpp
void solve(vector<vector<char>>& board) {
if (board.empty()) {
return;
}
int n = board.size();
int m = board[0].size();
// 遍历边界,将边界上的 'O' 及与其相邻的 'O' 标记为 '#'
for (int i = 0; i < n; i++) {
dfs(board, i, 0);
dfs(board, i, m - 1);
}
for (int j = 0; j < m; j++) {
dfs(board, 0, j);
dfs(board, n - 1, j);
}
// 遍历整个矩阵,将剩余的 'O' 替换为 'X',将 '#' 恢复为 'O'
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == '#') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
void dfs(vector<vector<char>>& board, int i, int j) {
int n = board.size();
int m = board[0].size();
if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] != 'O') {
return;
}
board[i][j] = '#';
dfs(board, i - 1, j);
dfs(board, i + 1, j);
dfs(board, i, j - 1);
dfs(board, i, j + 1);
}
```
这样,当你调用 `solve(board)` 后,矩阵 `board` 中被 'X' 围绕的区域里的 'O' 就会被替换为 'X'。希望对你有帮助!