問(wèn)題1091：0表示可通行，1表示不可通行，每走一步可以向上、下、左、右、左上、左下、右上、右下，共八個(gè)方向。求解從左上角到右下角的最短路徑長(zhǎng)度，如果無(wú)法到達(dá)，返回-1。

這題明顯可以用BFS進(jìn)行搜索，具體過(guò)程如下面動(dòng)圖所示。因?yàn)槊看嗡阉饕疾?code>8個(gè)方向，可能越出矩陣范圍，因此預(yù)處理時(shí)把矩陣周?chē)鷩弦蝗?code>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

運(yùn)行結(jié)果：