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，可以想象，如果让你在一棵树中找到达叶子节点的最短路径，一个可行的方法就是逐层遍历树，遇到的第一个叶子节点就是路径最短的叶子节点，因为其深度最低
但是用BFS做这道题我是有两个问题的：
第一个问题就是，如果某个节点可以是多个节点的子节点，该如何解决，例如，下图中，黄色节点既可以是红色节点的子节点，也可以是绿色节点的子节点，也可以是黑色节点的子节点（因为是它们的邻域节点），那么在做计算的时候，这个节点到底应该属于谁？
事实上，它属于谁都可以，因为这三个节点到黄色节点的距离都是1，所以在BFS过程中，谁第一个遇到该节点，这个节点就属于谁，后续其他节点就不能再访问该节点
第二个问题是，如果在某条路径中红色节点访问了黄色节点，按照BFS的做法，这两个节点就应该被标记为以访问，后续就不会再访问这两个节点了，那么问题就来了，我怎么能确定红色访问黄色节点就是最短路径中的一部分，而不是黄色访问红色节点？即这两个节点的访问顺序和结果无关吗？
访问顺序和结果当然是有关的，例如上图中，黑色-红色-黄色-蓝色就是一条路径，而反过来，黑色-黄色-红色就无法构成一条到达蓝色的路径了（规定只能走有颜色的邻域节点）。
但是，BFS是从浅到深遍历树的，也就是说，如果遍历的结果是红色访问黄色，那么红色节点一定在黄色节点的同一层或者上一层，不可能在黄色节点的下一层，也就是说，红色到黄色就是最短路径的组成部分，相反，黄色到红色就不一定。具体的，如果红色在黄色的上层，那么一定是红色到黄色，如果它们在同一层，那么红色到黄色与黄色到红色其实是一样的效果，试想一下，如果是在同一层，那么它们将一同进入BFS的队列中，而对BFS来说，同一层节点在这个队列中的顺序是无所谓的，先红还是先黄都是一样的。
事实上，这道题我一直想得很绕，很大一部分原因是我看到BFS后下意识就将其考虑成一棵树了，所以才会有很多问题，但是它并不是树，而是一个无向图，那么对于无向图来说，寻找单源最短路径就很简单了，无权值使用BFS，有权值使用迪杰斯特拉算法。那么上面那个图其实就可以画出一个无向图：
由于BFS的特性，其遍历的每个节点都是单源最短路径
代码如下：
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
if grid[0][0] == 1 or grid[-1][-1] == 1: return -1
stack = [(0, 0, 1)]
grid[0][0] = 1
while stack:
print(stack)
i, j, l = stack.pop(0)
if i == len(grid)-1 and j == len(grid)-1: return l
for x, y in [(i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1)]:
if 0<=x<len(grid) and 0<=y<len(grid) and grid[x][y] == 0:
stack.append((x, y, l+1))
grid[x][y] = 1
return -1BFS之所以有单源最短路径的特性，我的理解还是有点递归的思想在里面：对任意一个节点来说，从源到它的最短路径应该等于从源到它父节点的最短路径+1，BFS从源开始寻找最短路径，那么它后续遍历的节点必然还是最短路径。