1 minute read

130. Surrounded Regions

Difficulty: Medium

Related Topics: Array, DFS, BFS, Union Find, Matrix

Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Example 1:

Input: board = [[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]] Output: [[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]] Explanation: Notice that an ‘O’ should not be flipped if:

  • It is on the border, or
  • It is adjacent to an ‘O’ that should not be flipped. The bottom ‘O’ is on the border, so it is not flipped. The other three ‘O’ form a surrounded region, so they are flipped.

Example 2:

Input: board = [[“X”]] Output: [[“X”]]

Code:

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        directions = [[-1,0],[1,0],[0,-1],[0,1]] #left, right, up, down
        row = len(board)-1
        column = len(board[0])-1
        edges=[]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if i == 0 or i == len(board)-1 or j == 0 or j == len(board[0])-1:
                    edges.append([i,j])

        def dfs(board, edges):
            for edge in edges:
                stack = [edge]
                while len(stack) != 0:
                    s = stack.pop()
                    if board[s[0]][s[1]] == "O":
                        board[s[0]][s[1]] = "OO"
                        for i in directions:
                            if s[0]+i[0] >=0 and s[0]+i[0] <= row and s[1]+i[1] >=0 and s[1]+i[1] <= column:
                                stack.append([s[0]+i[0],s[1]+i[1]])
        dfs(board, edges)
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == "O":
                    board[i][j] = "X"
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == "OO":
                    board[i][j] = "O"
        
        return board

Feedbacks:

I first set the directions (left, right, up, and down). Since as I analyze this problem, I only need to check for the edges of the board, I first appended all of the edges indicies to the edges list. Then I used depth first search for all the edges. If edge is “X”, nothing changes. Else if the edge is “O”, I append its adjacent regions to stack and check whether they are “O” or not. If edge region is “O” and it has “O” in its adjacent regions, I change all of them by “OO”. After finishing search for all the edges, I need to replace the board. First replace “O” with “X”, then replace “OO” with “O”. Then, I can get the new board that “O” surrounded by “X” by four sides are flipped to “X” and others remain.

You may also enjoy