130. Surrounded Regions

Description

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

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

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input:

Output:

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        if(m == 0 || m == 1) return;
        
        int n = board[0].length;
        
        // replace all 'O' with '*'
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == 'O') board[i][j] = '*';
            }
        }
        
        // left side
        for(int i = 0; i < m; i++) {
            if(board[i][0] == '*') {
                dfs(board, m, n, i, 0, '*', 'O');
            }
        }
        // right side
        for(int i = 0; i < m; i++) {
            if(board[i][n-1] == '*') {
                dfs(board, m, n, i, n-1, '*', 'O');
            }
        }
        // top side
        for(int i = 0; i < n; i++) {
            if(board[0][i] == '*') {
                dfs(board, m, n, 0, i, '*', 'O');
            }
        }
        // bottom side
        for(int i = 0; i < n; i++) {
            if(board[m-1][i] == '*') {
                dfs(board, m, n, m-1, i, '*', 'O');
            }
        }
        
        // replace all '*' with 'X'
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == '*') board[i][j] = 'X';
            }
        }
    }
    
    private void dfs(char[][] board, int m, int n, int i, int j, 
                        char prev, char newv) {
        if(i < 0 || i >= m || j < 0 || j >= n) return;
        
        if(board[i][j] != prev) return;
        
        board[i][j] = newv;
        
        dfs(board, m, n, i+1, j, '*', 'O');
        
        dfs(board, m, n, i-1, j, '*', 'O');
        
        dfs(board, m, n, i, j+1, '*', 'O');
        
        dfs(board, m, n, i, j-1, '*', 'O');
    }
    
}

Follow up