在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。
一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, …, C_k 组成：
相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角） C_1 位于 (0, 0)（即，值为 grid[0][0]） C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]） 如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0） 返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。
示例 1：
输入：[[0,1],[1,0]] 输出：2
示例 2：
输入：[[0,0,0],[1,1,0],[1,1,0]]
输出：4
提示：
1 <= grid.length == grid[0].length <= 100 grid[i][j] 为 0 或 1
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
看到这道题，我第一印象就是bfs。 然后写了半天发现俺不会： 又研究了下原理
void BFS() { 定义队列; 定义备忘录，用于记录已经访问的位置； 判断边界条件，是否能直接返回结果的。 将起始位置加入到队列中，同时更新备忘录。 while (队列不为空) { 获取当前队列中的元素个数。 for (元素个数) { 取出一个位置节点。 判断是否到达终点位置。 获取它对应的下一个所有的节点。 条件判断，过滤掉不符合条件的位置。 新位置重新加入队列。 } } } 代码 struct Node { int x; int y; }; class Solution { public: int shortestPathBinaryMatrix(vector<vector<int>>& grid) { int ans = 0; queue<Node> myQ; // BFS一般通过队列方式解决 int M = grid.size(); int N = grid[0].size(); // 先判断边界条件，很明显，这两种情况下都是不能到达终点的。 if (grid[0][0] == 1 || grid[M - 1][N - 1] == 1) { return -1; } // 备忘录，记录已经走过的节点 vector<vector<int>> mem(M, vector<int>(N, 0)); myQ.push({0, 0}); mem[0][0] = 1; // 以下是标准BFS的写法 while (!myQ.empty()) { int size = myQ.size(); for (int i = 0; i < size; i++) { Node currentNode = myQ.front(); int x = currentNode.x; int y = currentNode.y; // 判断是否满足退出的条件 if (x == (N - 1) && y == (M - 1)) { return (ans + 1); } // 下一个节点所有可能情况 vector<Node> nextNodes = {{x + 1, y}, {x - 1, y}, {x + 1, y - 1}, {x + 1, y + 1}, {x, y + 1}, {x, y - 1}, {x - 1, y - 1}, {x - 1, y + 1}}; for (auto& n : nextNodes) { // 过滤条件1： 边界检查 if (n.x < 0 || n.x >= N || n.y < 0 || n.y >= M) { continue; } // 过滤条件2：备忘录检查 if (mem[n.y][n.x] == 1) { continue; } // 过滤条件3：题目中的要求 if (grid[n.y][n.x] == 1) { continue; } // 通过过滤筛选，加入队列！ mem[n.y][n.x] = 1; myQ.push(n); } myQ.pop(); } ans++; } return -1; } }; 作者：hank-36 链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix/solution/biao-zhun-de-bfsjie-fa-duo-lian-xi-jiu-hui-zhang-w/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。其实写着写着也不太会，看了半天例子，主要是总循环判断队列是不是空，队列不是空就把队列里的一个个拿出来，然后把队列周围一步可以加的数加进去，我那个三个判断条件没找好，备忘录是一定需要定义的。
struct Node{ int x; int y; }; class Solution { public: int shortestPathBinaryMatrix(vector<vector<int>>& grid) { //开始准备阶段，定义各种参数 int count = 0; //计数 int n = grid.size(); int m = grid[0].size(); //定义数组 //开始判定条件 if((grid[0][0]==1)|| (grid[m-1][n-1] ==1)) return -1; //备忘录 vector<vector<int>> already(m, vector<int>(n, 0)); //创建一个vector,里面装了m个vector<int>，vector<int>又装了N个0 //开始模拟第一步，定义BFS的队列，进入矩阵 queue<Node> myQ; // BFS一般通过队列方式解决 myQ.push({0, 0}); already[0][0] = 1;//表示已经遍历 count++; while(!myQ.empty()){ int size = myQ.size(); for (int i = 0; i < size; i++) { Node data = myQ.front(); //拿到队列第一个值 int x = data.x; int y = data.y; if((x==n-1) && (y==m-1)) return count; //下一步的情况 vector<Node> next = {{x + 1, y}, {x - 1, y}, {x + 1, y - 1}, {x + 1, y + 1}, {x, y + 1}, {x, y - 1}, {x - 1, y - 1}, {x - 1, y + 1}}; for (auto& n1 : next){ // 过滤条件1： 如果边界超出就不能走 if (n1.x < 0 || n1.x >= n || n1.y < 0 || n1.y >= m) { continue; } // 过滤条件2：如果走过就不能走 if (already[n1.y][n1.x] == 1) { continue; } // 过滤条件3：如果有阻拦就不能走 if (grid[n1.y][n1.x] == 1) { continue; } already[n1.y][n1.x] = 1; myQ.push(n1); } myQ.pop(); } count++; } return -1; } };和官方答案差不多嘿嘿。
学习总结：BFS的使用，vector的vector(m,n)就是数据n有m个。
