被围绕的区域(Leetcode 130)

题目分析

   这道题目难度不大，是一个经典的图搜索问题，如何搜索才能达到最高的效率呢？这题有一个巧妙的方法。

DFS

图的搜索方法，深度优先搜索，但是这道题的技巧在于，从边缘点进行搜索，搜索到的点都是不被围绕的点。为了记录搜索的路径，常用方法是建立一个哈希表，存放已经经过的点，这里为了节省空间，使用了一种技巧，将搜索过的点改为A，那么下次再搜索到时也不会进行重复搜索，非常方便。时间复杂度为$O(m \times n)$，空间复杂度为$O(m \times n)$

class Solution:
    def solve(self, board):
        """
        Do not return anything, modify board in-place instead.
        """
        def dfs(x, y):
            board[x][y] = "A"
            for i, j in direction:
                new_x, new_y = x + i, y + j
                if 0 <= new_x < row and 0 <= new_y < col and board[new_x][new_y] == "O":
                    dfs(new_x, new_y)

        if not board:
            return board
        direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        row, col = len(board), len(board[0])
        for i in range(row):
            if board[i][0] == "O":
                dfs(i, 0)
            if board[i][col - 1] == "O":
                dfs(i, col - 1)
        for j in range(col):
            if board[0][j] == "O":
                dfs(0, j)
            if board[row - 1][j] == "O":
                dfs(row - 1, j)
        for i in range(row):
            for j in range(col):
                if board[i][j] == "A":
                    board[i][j] = "O"
                elif board[i][j] == "O":
                    board[i][j] = "X"

        return board

BFS

这道题也可以类似的使用BFS来进行求解，解题思路大致相同。

class Solution:
    def solve(self, board):
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return board
        direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        row, col = len(board), len(board[0])

        queue = deque()

        for i in range(row):
            if board[i][0] == "O":
                queue.append((i, 0))
            if board[i][col - 1] == "O":
                queue.append((i, col - 1))
        for j in range(col):
            if board[0][j] == "O":
                queue.append((0, j))
            if board[row - 1][j] == "O":
                queue.append((row - 1, j))

        while queue:
            x, y = queue.popleft()
            board[x][y] = "A"
            for i, j in direction:
                new_x, new_y = x + i, y + j
                if 0 <= new_x < row and 0 <= new_y < col and board[new_x][new_y] == "O":
                    queue.append((new_x, new_y))

        for i in range(row):
            for j in range(col):
                if board[i][j] == "A":
                    board[i][j] = "O"
                elif board[i][j] == "O":
                    board[i][j] = "X"

        return board

刷题总结

  路径搜索问题已经不想重复强调了，重要！重要！重要！