LeetCode June Challenge - Day 17

Problem: LeetCode June Challenge - Day 17

Ideas:

  1. A region is not surrounded if some element is in the border.
  2. A region is a connected component in an undirected graph.
  3. You only need to check the ‘O’ in the borders and find it’s connected components. Here are some details of my implementation:
    • I use the board as a visited array, flipping ‘O’ to ‘1’.
    • After this, the board has ‘1’ where there should be ‘O’, and ‘O’ where there should be ‘X’. Just flip these values.

Solution:

class Solution {
    int n, m;

    void dfs(int i, int j, vector<vector<char>>& b){
        b[i][j] = '1';
        if(i < n-1 && b[i+1][j] == 'O') dfs(i+1, j, b);
        if(i > 0 && b[i-1][j] == 'O') dfs(i-1, j, b);
        if(j < m-1 && b[i][j+1] == 'O') dfs(i, j+1, b);
        if(j > 0 && b[i][j-1] == 'O') dfs(i, j-1, b);
    }

public:
    void solve(vector<vector<char>>& board) {
        n = board.size();
        if(n == 0) return;
        m = board[0].size();

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

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