130. Surrounded Regions
C++，dfs，反向。
题意就是找出被‘X’完全包围的‘O’的区域，填充为‘X’。
解决思路就是反向找出没有完全被‘X’完全包围的‘O’的区域，标记一下，然后没有标记的就是要被填充的。
-
思路就是绕着矩阵的最外圈转一圈，碰到‘O’，说明这里可以往里进行深搜；
- 将深搜经过的所有‘O’都标记成‘Y’；
- 外圈深搜完成后，所有没有被包围的‘O’都已经标记成了‘Y’；
- 将所有‘Y’填充为‘O’，所有‘O’填充为‘X’。
代码：
class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty()) return ;
vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};
int left = 0, top = 0, right = (int)board[0].size() - 1, bottom = (int)board.size() - 1;
int i = top, j = left;
for (i = top; j <= right; j++) {
if (board[i][j] == 'O')
dfs(board, i, j, bottom, right, dx, dy);
}
for (j = right; i <= bottom; i++) {
if (board[i][j] == 'O')
dfs(board, i, j, bottom, right, dx, dy);
}
for (i = bottom; j >= left; j--) {
if (board[i][j] == 'O')
dfs(board, i, j, bottom, right, dx, dy);
}
for (j = left; i >= top; i--) {
if (board[i][j] == 'O')
dfs(board, i, j, bottom, right, dx, dy);
}
for (i = 0; i <= bottom; i++) {
for (j = 0; j <= right; j++) {
if (board[i][j] == 'Y')
board[i][j] = 'O';
else board[i][j] = 'X';
}
}
}
void dfs(vector<vector<char>>& board, int x, int y, int &bottom, int &right,
vector<int> &dx, vector<int> &dy) {
board[x][y] = 'Y';
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || ty < 0 || tx > bottom || ty > right)
continue;
if (board[tx][ty] == 'O') {
dfs(board, tx, ty, bottom, right, dx, dy);
}
}
}
};
