【leetcode】1091. Shortest Path in Binary Matrix

向右看齐 2022-01-10 06:13 172阅读 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.  `1 <= grid.length == grid[0].length <= 100`
> 2.  `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

转载于:https://www.cnblogs.com/seyjs/p/11044772.html