[Leetcode] Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

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

Analysis:

•  DFS find all 'O' not surrounded by 'X' (at or connected to the edge of the board ) and changed to '#'
•  Flip the remain 'O' into X
•  Flip the '#' back to 'O'

class Solution {
public:

 void flipRegion(vector<vector<char>> &board, int i, int j)
 {
  if (board[i][j] == 'O')
  {
   board[i][j] = '#';
   if (i < board.size() - 1 && board[i+1][j] == 'O')
    flipRegion(board, i + 1, j);
   if (j < board[0].size() - 1 && board[i][j+1] == 'O')
    flipRegion(board, i, j + 1);
   if (i > 0 && board[i-1][j] == 'O')
    flipRegion(board, i - 1, j);
   //why should be 1 rather than 0 here? 
   if (j > 1 && board[i][j-1] == 'O')
    flipRegion(board, i, j - 1);
  }
 }


    void solve(vector<vector<char>> &board) {
        
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[i].size(); j++)
            {
                //if it is at the edge of the board
                if ((i == 0 || i == board.size()-1 || j == 0 || j == board[i].size() - 1)
                && (board[i][j] == 'O'))
                {
                    //board[i][j] = '#';
                    flipRegion(board, i, j);
                }
                    
            }
        }

        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[i].size(); j++)
            {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == '#')
                    board[i][j] = 'O';    
            }
        }
        
    }
};