题目链接：https://leetcode.cn/problems/shortest-path-in-binary-matrix/description/
我的思路
尝试用dfs的思路，思维定势了，已知起点在左上角，终点在右下角，那么自然想到要找到最短路径，那只能往右或者往右下走，于是在dfs中设置了(i + 1, j)和(i + 1, j + 1)两个位置的考察，同时定义一个结果ans变量，当走到终点后，比较当前路径的长度distance和ans的大小，将更小的那个值保留，不断比较，找到最终的答案
但这样的想法存在两个问题：1. 可走的方向考虑欠妥，太理想化了，万一右边和右下的路都被挡住了，只能往右上或者向上走，那这样的做法就永远找不到正确的路径，这个问题非常致命，在这道题里应该要考察八个方向：上下左右、左上左下、右上右下；2. dfs的方法不是不可以，但是随着矩阵大小的增加，其遍历所需时间会呈指数级暴涨，很容易就出现超时，效率非常低
纠正
这道题应该用bfs(breadth-first search)的方法，广度优先算法，用到队列（queue）结构来进行遍历而非栈，按层次进行遍历。深度优先搜索和广度优先搜索都可以处理可达性问题，即从一个节点开始是否能达到另一个节点，dfs用到了递归的思路，但在实际工程应用中，递归的写法很少见到，一方面是难以理解，另一方面很容易遇到栈溢出的情况
这里我们用到python内置的队列来进行操作，从collections中导入deque，用q = deque([0,0,1]) 定义一个队列：
- 队列存放的是 当前层要访问的节点，在这里就是网格中的坐标
(row, col)，以及从起点走到这里的路径长度 - 每次从队首
popleft()取出一个位置，遍历它的 8 个可能方向（上下左右和对角线） - 如果新位置合法（没有越界、没有障碍、没有访问过），就把它加入队尾
append()，并记录步数 - BFS 保证了最先到达终点的路径一定是最短的，因为搜索是按层推进的
BFS 为什么能保证最短？关键点在于：
- 队列是先进先出，所以 BFS 是一层一层扩展的
- 以案例[[0,0,0],[1,1,0],[1,1,0]]为例，当把
(0,2,3)或(1,2,3)入队时，steps=3说明它们是从 起点出发，用 3 步到达的所有格子 - BFS 保证 所有
steps=3的节点都在steps=4之前被处理，先将(0,2,3)出队，因为此时(1,2)已经被访问过了，在队列中，所以从(0,2)开始不会再往下走，(0,2,3)出队后，之后没有能走通的路，那么这个元素就不管了，消失，继续处理之后的元素。这一步背后的逻辑是，在从起点开始能走3步的情况下，能到达(0,2)和(1,2)这两个位置，原来(0,2)可以继续往下走到(1,2)，这样就要4步，但我已经在三步的时候走到了，并也将这个路径记录在了我的队列中，所以就不用管从(0,2)出发的情况了
所以，当终点 (2,2) 第一次被加入队列时，它一定是用 最少的步数到达的。之后即使 (2,2) 有别的路径能到，但那些路径的 steps 一定 ≥ 当前最小步数，所以不会比第一次更优
结果
时间复杂度：$O(N^2)$
空间复杂度：$O(N^2)$
已是最优解
