问题1091：BFS 二进制矩阵中的最短路径

问题1091：0表示可通行，1表示不可通行，每走一步可以向上、下、左、右、左上、左下、右上、右下，共八个方向。求解从左上角到右下角的最短路径长度，如果无法到达，返回-1。

这题明显可以用BFS进行搜索，具体过程如下面动图所示。因为每次搜索要考察8个方向，可能越出矩阵范围，因此预处理时把矩阵周围围上一圈1。

完整代码：

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:     
        m = len(grid)
        if grid[0][0] == 0 and grid[m-1][m-1] == 0:
            for i in range(m):
                grid[i].insert(0, 1)
                grid[i].append(1)
            grid.insert(0, [1]*(m+2))
            grid.append([1]*(m+2))
            queue = []
            queue.append([1,1])
            seen = set()
            seen.add((1,1))
        else:
            return -1
        while queue:
            vertex = queue.pop(0)
            nodes = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
            for node in nodes:
                new = (vertex[0]+node[0], vertex[1]+node[1])
                if grid[new[0]][new[1]] == 0 and new not in seen:                
                    queue.append(new)
                    seen.add(new)
                    grid[new[0]][new[1]] = grid[vertex[0]][vertex[1]] + 1
        return grid[m][m]+1 if (m, m) in seen else -1

运行结果：