Leetcode 130.被围绕的区域

Posted on |

130.被围绕的区域

题目

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

1
2
3
4
5
6
7
8
9
10
11
12
示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

方法

被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

将边界上及与边界上的’O’相连的’O’标记为’G’

Phase 1: “Save” every O-region touching the border, changing its cells to ‘S’.
Phase 2: Change every ‘G’ on the board to ‘O’ and everything else to ‘X’.

方法1：广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if len(board)==0:
            return
        m,n=len(board),len(board[0])

        def bfs(board,i,j):
            queue=collections.deque([[i,j]])
            board[i][j]='G'
            while queue:
                i,j=queue.popleft()
                for nr,nc in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
                    if 0<=nr<m and 0<=nc<n and board[nr][nc]=='O':
                        queue.append([nr,nc])
                        board[nr][nc]='G'

        for i in range(n):
            if board[0][i]=='O':
                bfs(board,0,i)
            if board[m-1][i]=='O':
                bfs(board,m-1,i)

        for i in range(m):
            if board[i][0]=='O':
                bfs(board,i,0)
            if board[i][n-1]=='O':
                bfs(board,i,n-1)

        for i in range(m):
            for j in range(n):
                if board[i][j]=='G':
                    board[i][j]='O'
                else:
                    board[i][j]='X'

方法2：深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if len(board)==0:
            return
        m,n=len(board),len(board[0])

        def dfs(board,i,j):
            if not 0<=i<m or not 0<=j<n or board[i][j]!='O':
                return
            board[i][j]='G'
            dfs(board,i+1,j)
            dfs(board,i-1,j)
            dfs(board,i,j+1)
            dfs(board,i,j-1)

        for i in range(n):
            if board[0][i]=='O':
                dfs(board,0,i)
            if board[m-1][i]=='O':
                dfs(board,m-1,i)

        for i in range(m):
            if board[i][0]=='O':
                dfs(board,i,0)
            if board[i][n-1]=='O':
                dfs(board,i,n-1)

        for i in range(m):
            for j in range(n):
                if board[i][j]=='G':
                    board[i][j]='O'
                else:
                    board[i][j]='X'