Leetcode 1091. Shortest Path in Binary Matrix

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

**解析：**Version 1，如果起始点为1，直接返回-1，否则，使用广度优先搜索，使用grid[i][j]=1来表示访问过的点，从左上角开始，遍历满足条件的8个方向上的点，并将其坐标以及当前的长度保存到队列中，并将其值置为1，即已经访问过该点。第一次访问到右下角点时即为最短距离。

• Version 1

class Solution:def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:if grid[0][0] == 1:return -1n = len(grid)queue = collections.deque()queue.append((0, 0, 1))while queue:i, j, count = queue.popleft()if i == n - 1 and j == n - 1:return countcount += 1if i > 0 and j > 0 and grid[i-1][j-1] == 0:grid[i-1][j-1] = 1queue.append((i-1, j-1, count))if i > 0 and grid[i-1][j] == 0:grid[i-1][j] = 1queue.append((i-1, j, count))if i > 0 and j < n-1 and grid[i-1][j+1] == 0:grid[i-1][j+1] = 1queue.append((i-1, j+1, count))if j > 0 and grid[i][j-1] == 0:grid[i][j-1] = 1queue.append((i, j-1, count))if j < n-1 and grid[i][j+1] == 0:grid[i][j+1] = 1queue.append((i, j+1, count))if i < n-1 and j > 0 and grid[i+1][j-1] == 0:grid[i+1][j-1] = 1queue.append((i+1, j-1, count))if i < n-1 and grid[i+1][j] == 0:grid[i+1][j] = 1queue.append((i+1, j, count))if i < n-1 and j < n-1 and grid[i+1][j+1] == 0:grid[i+1][j+1] = 1queue.append((i+1, j+1, count))return -1

Reference

1. https://leetcode.com/problems/shortest-path-in-binary-matrix/