/** * https://oj.leetcode.com/problems/surrounded-regions/ * 从四个边界的'O'出发,它们所能到达的'O'就是没有被包围的'O'。 * 所以,该题能够用BFS遍历或者DFS遍历。 */ class Solution { public: void solve(vector<vector<char>> &board) { int row = board.size(); if(row <= 2){ return; } int col = board[0].size(); if(col <=2){ return; } int i = 0; int j = 0; if(row > 2 && col > 2){ for(i = 0; i < row; i++){ if(board[i][0] == 'O'){ board[i][0] = 'P'; if(board[i][1] == 'O'){ search(i, 1, row, col, board); } } if(board[i][col - 1] == 'O'){ board[i][col - 1] = 'P'; if(board[i][col - 2] == 'O'){ search(i, col - 2, row, col, board); } } }//end of for(i = 0; i < row; i++) for(j = 0; j < col; j++){ if(board[0][j] == 'O'){ board[0][j] = 'P'; if(board[1][j] == 'O'){ search(1, j, row, col, board); } } if(board[row - 1][j] == 'O'){ board[row - 1][j] = 'P'; if(board[row - 2][j] == 'O'){ search(row - 2, j, row, col, board); } } } //end of for(j = 0; j < col; j++) }//end of if(row >2 && col > 2) for(i = 0; i < row; i++){ for(j = 0; j < col; j++){ if(board[i][j] == 'P'){ board[i][j] = 'O'; } else { board[i][j] = 'X'; } } } } //search(1, j, row, col, board); void search(int i, int j, const int row, const int col, vector<vector<char>> &board){ board[i][j]='P'; if(i - 1 > 0 && board[i - 1][j] == 'O'){ search(i - 1, j, row, col, board); } if(i + 1 < row - 1 && board[i + 1][j] == 'O'){ search(i+1, j, row, col, board); } if(j - 1 > 0 && board[i][j - 1] == 'O'){ search(i, j - 1, row, col, board); } if(j + 1 < col && board[i][j + 1] == 'O'){ search(i, j + 1, row, col, board); } } };