130 - Surrounded Regions

#medium

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

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

Example 1:

Input: board = [ ["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"] ]
Output: [ ["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"] ]
Explanation: Notice that an 'O' should not be flipped if:
=> It is on the border, or
=> It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.

Example 2:
Input: board = [ ["X"] ]
Output: [ ["X"] ]

1. 四邊訪問圈圈

class Solution {
public:
    void dfs( vector<vector<char>> & board, int m, int n, int i, int j ) {
        if ( i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O' ) return;
        board[i][j] = '#';
        dfs( board, m, n, i - 1, j );
        dfs( board, m, n, i + 1, j );
        dfs( board, m, n, i, j - 1 );
        dfs( board, m, n, i, j + 1 );
    }

    void solve(vector<vector<char>>& board) {
        int m = board.size();
        int n = board[0].size();
        for ( int j = 0; j < n; j++ ){
            if ( board[0][j] == 'O' ) dfs( board, m, n, 0, j );
            if ( board[m-1][j] == 'O') dfs( board, m, n, m - 1, j );
        }

        for ( int i = 0; i < m; i++ ) {
            if ( board[i][0] == 'O') dfs( board, m, n, i, 0 );
            if ( board[i][n-1] == 'O' ) dfs( board, m, n, i, n - 1 );
        }

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