算法

Shortest Path in Binary Matrix

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

以下为我的思考过程：

我首先想到能否使用动态规划解题，因为，假设要求解的坐标为(i,j)，那么我只需要知道其邻域八个坐标的解，即对于给定任意grid中的坐标，如果该坐标值为0，则我只需使用 1+min(邻域坐标最短路径)即可求解。但细想一下也不对，因为这八个坐标并不全是求解坐标的子问题，因为如果要满足子问题的规模，则子规模的坐标必须都大于或者小于求解坐标，显然邻域坐标中，有些大于(i,j)，有些小于(i,j)。这说明这题应该不适用于动态规划。

于是又想，既然是求解路径，dfs应该是可行的，于是写代码：

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[-1][-1] == 1 or grid[0][0]: return -1
        def dfs(i, j, path):
            if (i, j) in path or i < 0 or i > len(grid)-1 or j < 0 or j > len(grid)-1: return -1
            if i == len(grid)-1 and j == len(grid)-1: return 1
            return -1 if grid[i][j] != 0 else 1 + min(filter(lambda x: x>0, [dfs(i-1, j-1, path+[(i, j)]), dfs(i-1, j, path+[(i, j)]), dfs(i-1, j+1, path+[(i, j)])
                , dfs(i, j-1, path+[(i, j)]), dfs(i, j+1, path+[(i, j)])
                , dfs(i+1, j-1, path+[(i, j)]), dfs(i+1, j, path+[(i, j)]), dfs(i+1, j+1, path+[(i, j)])]), default=-2)

        return dfs(0, 0, [])

但这个会超时，原因在于，dfs会遍历所有可能的路径，然后找到一条最短路径。有没有直接找最短路径的方法呢？那就是BFS，可以想象，如果让你在一棵树中找到达叶子节点的最短路径，一个可行的方法就是逐层遍历树，遇到的第一个叶子节点就是路径最短的叶子节点，因为其深度最低