130.md

Surrounded Regions

Description

link

---

Solution BFS

save存储的是目前所有的边界坐标，在循环的过程中，只要发现有满足边界的O那么上下左右都可以成为新的边界，然后将这些所有的边界O保存即可，本质是BFS

---

Code

Complexity T : O(mn) M : O(1)

class Solution:
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:
            return None
        
        m = len(board)
        n = len(board[0])
        
        save = [ij for k in range(max(m, n)) for ij in ((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, j - 1), (i + 1, j), (i, j + 1)
            
        board[:] = [['XO'[c == 'S'] for c in row] for row in board]