130. Surrounded Regions

Loading...LeetCode

和 number of islands 类似的思路，只是搜的同时要记录island region，搜完成了一个岛之后，要判断下是不是有node on border，有的话就不capture，没有就capture.

GitBook

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]: return 0
            
        visited = set()
        w, h = len(board), len(board[0])
        
        def anyOnBorder(region):
            for x, y in region:
                if (x==0 or x==w-1 or y==0 or y==h-1):
                    return True
            return False
            
        def validNeighbors(x, y):
            applicants = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
            valid = []
            for a in applicants:
                if a not in visited and a[0]>=0 and a[0]<w and a[1]>=0 and a[1]<h:
                    valid.append(a)
            return valid
        
        for i in range(w):
            for j in range(h):
                if (i, j) in visited:
                    continue
                else:
                    if board[i][j] == 'O':
                        region = [(i,j)]
                        queue = collections.deque([(i,j)])
                        while queue:
                            x, y = queue.popleft()
                            visited.add((x,y))
                            togo = validNeighbors(x, y)
                            if togo:
                                for x_next, y_next in togo:
                                    visited.add((x_next, y_next))
                                    if board[x_next][y_next] == 'O':
                                        region.append((x_next, y_next))
                                        queue.append((x_next, y_next))
                        if not anyOnBorder(region):
                            for x, y in region:
                                board[x][y] = 'X'
        return board