Graph Problems

08 Nov 2018 in Programming on Graph, Interview, Python

##Capture Regions on Board

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

Note: The input is

['XXX', 
 'XOX', 
 'XXX']

a list of string. That means you can’t do inplace replacement. Better to convert it to a list of lists

class Solution:
    def fill(self, A, x, y, prevIcon, currIcon):
        N = len(A)
        M = len(A[0])
        if x < 0 or x >= N or y < 0 or y >= M:
            return
        if A[x][y] != prevIcon:
            return 
        
        A[x][y] = currIcon
        # visit 4 directions north, east, south, west
        self.fill(A, x+1, y, prevIcon, currIcon)
        self.fill(A, x, y+1, prevIcon, currIcon)
        self.fill(A, x-1, y, prevIcon, currIcon)
        self.fill(A, x, y-1, prevIcon, currIcon)
        
        
    # @param A : list of list of chars
    def solve(self, A):
        if not isinstance(A, list): return 0
        if len(A[0]) == 1: return 0
        N = len(A)
        M = len(A[0])
        
        A_prime = [['O']*M for _ in range(N)]
        for i in range(N):
            for j in range(M):
                A_prime[i][j] = A[i][j]
        A_prime
        # replace all O with -
        
        # assign all O to -
        for i in range(N):
            for j in range(M):
                if A_prime[i][j] == 'O': A_prime[i][j] = '-'
        
        # assign all - at the edges to O
        for i in range(N):
            self.fill(A_prime, i, 0, '-', 'O')
            self.fill(A_prime, i, M-1, '-', 'O')
        for j in range(M):
            self.fill(A_prime, 0, j, '-', 'O')
            self.fill(A_prime, N-1, j, '-', 'O')
        
        # assign all - to X
        for i in range(N):
            for j in range(M):
                if A_prime[i][j] == '-': A_prime[i][j] = 'X'
        for i in range(N):
            A[i] = ''.join(A_prime[i])
        return A