My python solution


  • 3
    Y

    Here is my python solution. ~ 500 ms. Not as fast as others' Java or C++ code. Not sure if it is because my implementation or the python interpreter.

    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):
            
            N = len(board)
            if N <= 2: return
        
            M = len(board[0])
            if M <= 2: return
            
            def dfs(i, j):
                S = [(i, j)]    # dfs stack
                while S:
                    p, q = S.pop()
                    board[p][q] = 'B'
                    
                    # up, down, left, right
                    if p > 0 and board[p - 1][q] == 'O':        S.append((p - 1, q))
                    if p < N - 1 and board[p + 1][q] == 'O':    S.append((p + 1, q))
                    if q > 0 and board[p][q - 1] == 'O':        S.append((p, q - 1))
                    if q < M - 1 and board[p][q + 1] == 'O':    S.append((p, q + 1))
                
            # top and bottom
            for j in xrange(M):
                if board[0][j] == 'O':      dfs(0, j)
                if board[N - 1][j] == 'O':  dfs(N - 1, j)
                
            # left and right
            for i in xrange(1, N - 1):
                if board[i][0] == 'O':      dfs(i, 0)
                if board[i][M - 1] == 'O':  dfs(i, M - 1)
                
            # final mark
            for i in xrange(N):
                for j in xrange(M):
                    if board[i][j] == 'O':      board[i][j] = 'X'
                    elif board[i][j] == 'B':    board[i][j] = 'O'

  • 0
    L

    like this solution!


  • 0
    C

    Here is mine:

    def solve(self, board):
        if not board:
            return
        not_captured = set()
        m, n = len(board), len(board[0])
        walls = list(itertools.product((0, m - 1), range(n))) + list(itertools.product(range(1, m - 1), (0, n - 1)))
        
        # dfs from the edge
        for i, j in walls:
            if board[i][j] == 'O' and (i, j) not in not_captured:
                self.dfs(i, j, not_captured, board)
        
        # mark the captured
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if board[i][j] == 'O' and (i, j) not in not_captured:
                    board[i][j] = 'X'
    
    def dfs(self, i, j, table, board):
        m, n = len(board), len(board[0])
        is_valid = lambda x, y: -1 < x < m and -1 < y < n  
        stack = [(i, j)]
        while stack:
            i, j = stack.pop()
            table.add((i, j))
            for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                if is_valid(x, y) and board[x][y] == 'O' and (x, y) not in table:
                    stack.append((x, y))

  • 0
    S

    it is a typical BFS...


  • 0
    H

    My recursive DFS solution is as follows though Run Time Error in this oj test:

    class Solution:
        # @param {character[][]} board
        # @return {void} Do not return anything, modify board in-place instead.
        def solve(self, board):
            if not board:
                return
            rows = len(board)
            cols = len(board[0])
            # merge Os on left&right border
            for i in xrange(rows):
                if board[i][0] == 'O':
                    self.merge(board, i, 0)
                if board[i][cols-1] == 'O':
                    self.merge(board, i, cols-1)
            # merge Os on top&bottom border
            for j in xrange(cols):
                if board[0][j] == 'O':
                    self.merge(board, 0, j)
                if board[rows-1][j] == 'O':
                    self.merge(board, rows-1, j)
            # process the board
            for i in xrange(rows):
                for j in xrange(cols):
                    if board[i][j] == 'O':
                        board[i][j] = 'X'
                    elif board[i][j] == '+':
                        board[i][j] = 'O'
        
        def merge(self, board, i, j):
            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != 'O':
                return
            board[i][j] = '+'
            
            self.merge(board, i-1, j)
            self.merge(board, i+1, j)
            self.merge(board, i, j-1)
            self.merge(board, i, j+1)
    

    My BFS solution passed the oj test with 192ms:

    class Solution:
        def __init__(self):
            self.queue = []
        # @param {character[][]} board
        # @return {void} Do not return anything, modify board in-place instead.
        def solve(self, board):
            if not board:
                return
            rows = len(board)
            cols = len(board[0])
    
            for i in xrange(rows):
                if board[i][0] == 'O':
                    self.bfs(board, i, 0)
                if board[i][cols-1] == 'O':
                    self.bfs(board, i, cols-1)
            
            for j in xrange(cols):
                if board[0][j] == 'O':
                    self.bfs(board, 0, j)
                if board[rows-1][j] == 'O':
                    self.bfs(board, rows-1, j)
            
            for i in xrange(rows):
                for j in xrange(cols):
                    if board[i][j] == 'O':
                        board[i][j] = 'X'
                    elif board[i][j] == '+':
                        board[i][j] = 'O'
        
        def bfs(self, board, i, j):
            n = len(board[0])
            # fill current cell and then neighbors
            self.fillCell(board, i, j)
            while self.queue:
                cur = self.queue[0]
                self.queue = self.queue[1:]
                x, y = cur / n, cur % n
                
                self.fillCell(board, x-1, y)
                self.fillCell(board, x+1, y)
                self.fillCell(board, x, y-1)
                self.fillCell(board, x, y+1)
        
        def fillCell(self, board, i, j):
            m, n = len(board), len(board[0])
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
                return
            # add current cell to queue and process neighbors in bfs
            self.queue.append(i*n+j)
            board[i][j] = '+'

  • 0
    M

    The post was indeed a BFS instead of DFS

    No, it's obviously DFS, not BFS.


  • 0
    H

    @ManuelP Alright, my bad. I was a little bit confused when I glanced that all adjacent Os were found at one time. As BFS would process all those neighbors in the next round, the original post just processed one at a time, which should be DFS. Thanks for the correction:P


  • 0
    M

    I'm not quite sure what you mean with "process" and "the next round", but I'd say the main point is that it uses a stack rather than a queue. At least that's what I'm always looking for first.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.