题目描述
Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
Example1:
X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X
解题思路
- dfs搜索
- 一种方法是遍历中间的O，如果没有到达边缘，那么将结果都变成X即可，如果到达了边缘，将之前变成X的再变回来。
- 在网上看到大家普遍的做法是扫矩阵的四条边，如果有O，则用 DFS 遍历，将所有连着的O都变成另一个字符，
- 比如 $，这样剩下的O都是被包围的，然后将这些O变成X，把$变回O就行了
class Solution {
public:
void solve(vector<vector<char>>& board) {
int row = board.size();
if(row == 0){
return;
}
int col = board[0].size();
bool isVisit[row * col]; // 元素是可以重复访问的
for(int i = 0; i < row * col; i++){
isVisit[i] = false;
}
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if((i == 0 || j == 0 || i == row - 1 || j == col - 1) && (board[i][j] == 'O')){
dfs(i, j, row, col, board);
}
}
}
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(board[i][j] == 'O'){
board[i][j] = 'X';
}else if(board[i][j] == '#'){
board[i][j] = 'O';
}
}
}
}
void dfs(int r, int c, int row, int col, vector<vector<char>>& board){
if(r < 0 || r >= row || c < 0 || c >= col || board[r][c] == 'X' || board[r][c] == '#'){
return;
}
// isVisit[r * col + c] = true;
board[r][c] = '#';
// dfs(r + 1, c, row, col, board, isVisit);
// dfs(r - 1, c, row, col, board, isVisit);
// dfs(r, c + 1, row, col, board, isVisit);
// dfs(r, c - 1, row, col, board, isVisit);
dfs(r + 1, c, row, col, board);
dfs(r - 1, c, row, col, board);
dfs(r, c + 1, row, col, board);
dfs(r, c - 1, row, col, board);
}
};
判断的时候 记得即那个改后的一并判断
class Solution {
public:
void solve(vector<vector<char>>& board) {
int row = board.size();
if(row == 0){
return;
}
int col = board[0].size();
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if((i == 0 || j == 0 || i == row - 1 || j == col - 1) && board[i][j] == 'O' && board[i][j] != '$'){
dfs(i, j, row, col, board);
}
}
}
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(board[i][j] == '$'){
board[i][j] = 'O';
}else if(board[i][j] == 'O'){
board[i][j] = 'X';
}
}
}
}
void dfs(int r, int c, int row, int col, vector<vector<char>>& board){
if(r < 0 || r >= row || c < 0 || c >= col || board[r][c] == 'X' || board[r][c] == '$'){
return;
}
board[r][c] = '$';
dfs(r + 1, c, row, col, board);
dfs(r, c + 1, row, col, board);
dfs(r - 1, c, row, col, board);
dfs(r, c - 1, row, col, board);
}
};
class Solution {
public:
void solve(vector<vector<char>>& board) {
if(board.size() == 0){
return;
}
int row = board.size();
int col = board[0].size();
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if((i == 0 || j == 0 || i == row - 1 || j == col - 1) && (board[i][j] == 'O')){
dfs(i, j, row, col, board);
}
}
}
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(board[i][j] == 'O'){
board[i][j] = 'X';
}
if(board[i][j] == '$'){
board[i][j] = 'O';
}
}
}
}
void dfs(int r, int c, int row, int col, vector<vector<char>>& board){
if(board[r][c] == 'O'){
board[r][c] = '$';
if(r > 0 && board[r - 1][c] == 'O'){
dfs(r - 1, c, row, col, board);
}
if(r < row - 1 && board[r + 1][c] == 'O'){
dfs(r + 1, c, row, col, board);
}
if(c > 0 && board[r][c - 1] == 'O'){
dfs(r, c - 1, row, col, board);
}
if(c < col - 1 && board[r][c + 1] == 'O'){
dfs(r, c + 1, row, col, board);
}
}
}
};
解题思路
- dfs搜索
class Solution { public: void solve(vector<vector<char>>& board) { if(board.size() == 0){ return; } int row = board.size(); int col = board[0].size(); for(int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ if((i == 0 || j == 0 || i == row - 1 || j == col - 1) && (board[i][j] == 'O') && board[i][j] != '$'){ //不等于$表示已经经过dfs深搜了 dfs(i, j, row, col, board); } } } for(int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ if(board[i][j] == 'O'){ board[i][j] = 'X'; } if(board[i][j] == '$'){ board[i][j] = 'O'; } } } } void dfs(int r, int c, int row, int col, vector<vector<char>>& board){ if(r < 0 || r >= row || c < 0 || c >= col || board[r][c] == 'X' || board[r][c] == '$'){ return; } if(board[r][c] == 'O'){ board[r][c] = '$'; dfs(r - 1, c, row, col, board); dfs(r + 1, c, row, col, board); dfs(r, c - 1, row, col, board); dfs(r, c + 1, row, col, board); } } };
