LeetCode (Python): 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

Solution:

We use backtracking to identify the elements not surrounded by 'X' and we mark those with a temporal symbol ('$'). The elements not surrounded by 'X' means that exists a path of elements 'O' to a border. So we start the backtracking algorithm with the boarders.

The last thing is replacing the temporal element by 'O' and the rest elements to 'X'.

class Solution:
    # @param board, a 2D array
    # Capture all regions by modifying the input board in-place.
    # Do not return any value.
    def solve(self, board):
        if len(board)==0:
            return
        for row in range(0,len(board)):
            self.mark(board,row,0)
            self.mark(board,row,len(board[0])-1)
        for col in range(0, len(board[0])):
            self.mark(board, 0, col)
            self.mark(board, len(board)-1, col)
        
        for row in range(0,len(board)):
            for col in range(0, len(board[0])):
                if board[row][col]=='$':
                    board[row][col] = 'O'
                else:
                    board[row][col] = 'X'
        
    def mark(self, board, row, col):
        stack = []
        nCols= len(board[0])
        stack.append(row*nCols+col)
        while len(stack)>0:
            position = stack. pop()
            row = position // nCols
            col = position % nCols
            if board[row][col] != 'O':
                continue
            board[row][col] = '$'
            if row>0:
                stack.append((row-1)*nCols+col)
            if row< len(board)-1:
                stack.append((row+1)*nCols+col)
            if col>0: 
                 stack.append(row*nCols+col-1)
            if col < nCols-1:
                stack.append(row*nCols+col+1)