【leetcode】1091. Shortest Path in Binary Matrix-蒲公英云

【leetcode】1091. Shortest Path in Binary Matrix

向右看齐 2022-01-10 06:13 287阅读 0赞

题目如下：

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:

Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)
C_1 is at location (0, 0) (ie. has value grid[0][0])
C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])
If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).

Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.

Example 1:
Input: [[0,1],[1,0]]
Output: 2
Example 2:
Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Note:

1 <= grid.length == grid[0].length <= 100
grid[r][c] is 0 or 1

解题思路：典型的BFS问题。从起点开始依次计算每个方格到达的最小值即可。这里用visit[i][j]记录从起点开始到(i,j)的最短路径，在BFS的过程中，可能有多条路径都能到达(i,j)，因此只要有更短的走法能到达(i,j)，就需要把(i,j)重新加入到队列中。

代码如下：

class Solution(object):
    def shortestPathBinaryMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if grid[0][0] == 1:
            return -1
        visit = []
        val = []
        for i in grid:
            visit.append([0] * len(i))
            val.append([0] * len(i))
        visit[0][0] = 1
        queue = [(0,0)]
        direction = [(0,1),(0,-1),(1,0),(1,-1),(-1,1),(-1,-1),(1,1),(1,-1)]
        while len(queue) > 0:
            x,y = queue.pop(0)
            for (i,j) in direction:
                if x + i >= 0 and x+i < len(grid) and y + j >= 0 and y + j < len(grid[0]) \
                    and grid[x + i][y+j] == 0 and (visit[x+i][y+j] == 0 or visit[x+i][y+j] - 1 > visit[x][y]):
                    queue.append((x+i,y+j))
                    visit[x+i][y+j] = visit[x][y] + 1
        return visit[-1][-1] if visit[-1][-1] > 0 else -1