477-被围绕的区域
思路
先从外围开始,身处外围的 O 是无法被包围的,同理,与一个无法被包围的 O 相连的 O 也是无法被包围的。
- 从外围开始,若遇到外围的 O,则将其标记为 #,意味无法被包围的 O
- 接着从这个 O 开始,使用深度遍历或广度遍历,将与之相连的 O 一并标记为 #
- 最后,遍历数组,将无法被包围的 O,此时被标记为 # 改为 O,其余 X 不变,可以被包围的O,此时被标记为O 变为 X
code
class Solution {
public:
/**
* @param board a 2D board containing 'X' and 'O'
* @return void
*/
void surroundedRegions(vector<vector<char>>& board) {
// Write your code here
int sizeRow = board.size();
if (sizeRow <= 0) {
return ;
}
int sizeCol = board[0].size();
if (sizeCol <= 0) {
return ;
}
// 从外围开始
int i = 0, j = 0;
for (j = 0; j < sizeCol; j++) {
// 上围
if (board[0][j] == 'O') {
DFS(board, 0, j);
}
// 下围
if (board[sizeRow - 1][j] == 'O') {
DFS(board, sizeRow - 1, j);
}
}
for (i = 0; i < sizeRow; i++) {
// 左围
if (board[i][0] == 'O') {
DFS(board, i, 0);
}
// 右围
if (board[i][sizeCol - 1] == 'O') {
DFS(board, i, sizeCol - 1);
}
}
for (i = 0; i < sizeRow; i++) {
for (j = 0; j < sizeCol; 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) {
if (i < board.size() && j < board[0].size()) {
board[i][j] = '#';
if (i > 0 && board[i - 1][j] == 'O') {
DFS(board, i - 1, j);
}
if (j > 0 && board[i][j - 1] == 'O') {
DFS(board, i, j - 1);
}
if (i < board.size() - 1 && board[i + 1][j] == 'O') {
DFS(board, i + 1, j);
}
if (j < board[0].size() - 1 && board[i][j + 1] == 'O') {
DFS(board, i, j + 1);
}
}
}
};