给出一个由‘O’和‘X’组成的矩阵,在矩阵中的所有‘X’所在的行、列都需要变成‘O’。 如果在矩阵边界上的‘O’所在的行、列被‘X’包围,则这些‘O’也需要变成‘X’。
时间: 2023-08-07 18:32:26 浏览: 34
这是一个典型的图论问题,可以使用BFS或DFS来解决。具体思路如下:
首先遍历矩阵边界上的每一个点,如果该点为‘O’,则从该点开始进行BFS或DFS,将与该点相邻的所有‘O’都标记为特殊字符(比如$)。
接下来再遍历整个矩阵,将所有的‘O’变成‘X’,将所有的特殊字符($)变成‘O’即可。
代码如下(以BFS为例):
```
void bfs(vector<vector<char>>& board, int i, int j) {
int m = board.size(), n = board[0].size();
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') continue;
board[x][y] = '$';
q.push({x-1, y});
q.push({x+1, y});
q.push({x, y-1});
q.push({x, y+1});
}
}
void solve(vector<vector<char>>& board) {
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') bfs(board, i, 0);
if (board[i][n-1] == 'O') bfs(board, i, n-1);
}
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') bfs(board, 0, j);
if (board[m-1][j] == 'O') bfs(board, m-1, j);
}
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';
}
}
}
```
阅读全文