题解 | #被围绕的区域#

想做并查集的，结果dfs更容易

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型vector<vector<>> 
     * @return char字符型vector<vector<>>
     */
    vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
      if (board.empty()) {
        return board;
      }
      
      //  左右边界
      for (int i = 0; i < board.size(); ++i) {
        dfs(board, i, 0);
        dfs(board, i, board[0].size() - 1);
      }
        
      //  上下边界
      for (int i = 0; i < board[0].size(); ++i) {
        dfs(board, 0, i);
        dfs(board, board.size() - 1, i);
      }
      
      for (int i = 0; i < board.size(); ++i) {
        for (int j = 0; j < board[0].size(); ++j) {
          if (board[i][j] == 'O') {
            board[i][j] = 'X';
          }
          if (board[i][j] == 'A') {
            board[i][j] = 'O';
          }
        }
      }
      
      return board;
    }
  private:
    void dfs(std::vector<std::vector<char>> &board, int x, int y) {
      if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) {
        return ;
      }
      
      if (board[x][y] == 'O') {
        board[x][y] = 'A';
        
        dfs(board, x - 1, y);
        dfs(board, x + 1, y);
        dfs(board, x, y - 1);
        dfs(board, x, y + 1);
      }
    }
};