给出一个由‘O’和‘X’组成的矩阵,在矩阵中的所有‘X’所在的行、列都需要变成‘O’。 如果在矩阵边界上的‘O’所在的行、列被‘X’包围,则这些‘O’也需要变成‘X’。 样例: 输入: [ ["X","X","X","X"], ["X","O","O","X"], ["X","X","O","X"], ["X","O","X","X"] ]
时间: 2023-07-07 15:38:54 浏览: 97
这是一个比较典型的矩阵遍历问题,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决。这里给出一个DFS的解法。
具体思路如下:
1. 遍历矩阵的边界,如果有'O'则从这个'O'开始进行DFS遍历,并将遍历到的所有'O'都标记为另一个字符(比如'#'),表示这些'O'不需要被替换成'X'。
2. 遍历整个矩阵,将所有剩余的'O'替换成'X',将所有标记为'#'的字符还原为'O'即可。
下面是代码实现:
```
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m = board.size();
if (m == 0) return;
int n = board[0].size();
if (n == 0) return;
// 遍历矩阵的边界
for (int i = 0; i < m; i++) {
dfs(board, i, 0, m, n);
dfs(board, i, n-1, m, n);
}
for (int j = 0; j < n; j++) {
dfs(board, 0, j, m, n);
dfs(board, m-1, j, m, n);
}
// 遍历整个矩阵,将剩余的'O'替换成'X',将标记为'#'的字符还原为'O'
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == '#') board[i][j] = 'O';
}
}
}
void dfs(vector<vector<char>>& board, int i, int j, int m, int n) {
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
board[i][j] = '#';
dfs(board, i-1, j, m, n);
dfs(board, i+1, j, m, n);
dfs(board, i, j-1, m, n);
dfs(board, i, j+1, m, n);
}
};
```