题目描述:
给你一个 m x n
的矩阵 board
,由若干字符 'X'
和 'O'
组成,捕获 所有 被围绕的区域:
- 连接:一个单元格与水平或垂直方向上相邻的单元格连接。
- 区域:连接所有
'O'
的单元格来形成一个区域。 - 围绕:如果您可以用
'X'
单元格 连接这个区域,并且区域中没有任何单元格位于board
边缘,则该区域被'X'
单元格围绕。
通过将输入矩阵 board
中的所有 'O'
替换为 'X'
来 捕获被围绕的区域。
示例 1:
输入:board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出:[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释:
在上图中,底部的区域没有被捕获,因为它在 board 的边缘并且不能被围绕。
示例 2:
输入:board = [["X"]]
输出:[["X"]]
提示:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j]
为'X'
或'O'
题目链接:
. - 力扣(LeetCode)
解题主要思路:
这题我觉得有两个麻烦,第一个麻烦就是不好理解题目啥意思,其实题目的意思是:除了边边的 'O' 以及能跟其构成‘连接’的 'O',其余的全部改成 'X'。第二个麻烦就是理解完题目的意思后,怎么把符合条件的区域 'O' 和 不符合条件的区域 'O' 分隔开来,其实有个办法就是,咱们遍历边边的元素,如果有不符合条件的 'O'(边边的 'O' 以及能跟其构成‘连接’的 'O'),咱们把他改成于 'O' 'X' 无关的符号,譬如 '?' ,之后二维数组内的所有 'O' 都是符合条件的 'O'(即需要改为 'X' 的),数组内的所有 '?' 都是原本不符合条件的 'O' ,我们需要将其改回来。
解题代码:
class Solution {
public:typedef pair<int, int> PII;int dx[4]{0, 0, 1, -1};int dy[4]{1, -1, 0, 0};int m, n;void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();// 先将与边缘的‘O‘相连的全部改为’O‘、‘X’无关的符号,譬如'?';for (int i = 0; i < n; ++i) { // 第一行和最后一行if (board[0][i] == 'O') bfs(board, 0, i );if (board[m-1][i] == 'O') bfs(board, m-1, i);}for (int j = 0; j < m; ++j) { // 第一列和最后一列if (board[j][0] == 'O') bfs(board, j, 0);if (board[j][n-1] == 'O') bfs(board, j, n-1);}// 此时二维数组board里的全部'O'全部符合题目要求,可直接改成'X'for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (board[i][j] == '?') board[i][j] = 'O';else if (board[i][j] == 'O') board[i][j] = 'X';}}}void bfs(vector<vector<char>>& board, int r, int c){queue<PII> que;que.push(make_pair(r, c));board[r][c] = '?';while (que.size()) {auto [a, b] = que.front();que.pop();for (int i = 0; i < 4; ++i) {int x = a + dx[i];int y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {que.push(make_pair(x, y));board[x][y] = '?';}}}}
};