130.-surrounded-regions.md

130. Surrounded Regions

• Medium

• 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.

Analysis

We start from the 4 edges and look for those that are "O". Then if we saw an "O", we add the grids around it to the stack into which we will be looking at. If the grid is "O", we change it into "S". Then after we have searched that stack, we would have finished the part of searching.

After that, we would be changing every grid that contains "S" to be "O", then change all the other grids to be "X".

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return board
        
        m=len(board)
        n=len(board[0])
        save=[]
        for k in range(max(m,n)):
            save+=(0, k), (m-1, k), (k, 0), (k, n-1)
        while save:
            i,j=save.pop()
            if 0<=i<m and 0<=j<n and board[i][j]=="O":
                board[i][j]="S"
                save+=(i+1,j),(i-1,j),(i,j-1),(i,j+1)
        for i in range(m):
            for j in range(n):
                if board[i][j]=="S":
                    board[i][j]="O"
                else:
                    board[i][j]="X"