Surrounded Regions Leetcode


#1

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.

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

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.


#2

Start with the first/last row and first/last columns, mark all O as some character, in the below I program we use #. This basically takes out all O's which are supposed to be preserved. Now do a traversal, mark all # as O rest of them as X.

func solve(board [][]byte)  {
    if (len(board)<=1 || len(board[0])==1) { return }
    rows, cols := len(board), len(board[0])
    for i:=0;i<len(board[0]);i++{
        if board[0][i]=='O'{
            dfs(board, 0, i)
        }
        if board[rows-1][i]=='O'{
             dfs(board, rows-1, i)
        }
    }
    
    for i:=0;i<len(board);i++{
        if board[i][0]=='O'{
            dfs(board, i, 0)
        }
        if board[i][cols-1]=='O'{
             dfs(board, i, cols-1)
        }
    }
    
    for i:=0;i<len(board);i++{
        for j:=0;j<len(board[i]);j++{
            if board[i][j] == '#'{
                board[i][j] = 'O'
            } else {
                board[i][j] = 'X'
            }
        }
    }
}

var xy = [][]int{{0, 0}, {0, -1}, {-1, 0}, {0, 1}, {1,0}}

func dfs(board [][]byte, i, j int) {
    if(i<0 || j<0 || i>len(board)-1 || j>len(board[0])-1 || board[i][j]!='O'){ return }
    board[i][j] = '#'
    for a:=0;a<len(xy);a++{
        ax, ay := i+xy[a][0], j+xy[a][1]
        dfs(board, ax , ay)
    }
}