在一個 N × N 的方形網(wǎng)格中，每個單元格有兩種狀態(tài)：空（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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

?

2019.7.9:

做了，能跑出來幾個樣例，但是全0過不了，不知道為啥...? 感覺邏輯上沒啥錯誤，憂傷

class Solution { public:int shortestPathBinaryMatrix(vector<vector<int>>& grid) {int row = grid.size();if(row == 0) return -1;int col = grid[0].size();if(grid[0][0] == 1 || grid[row-1][col-1] == 1) return -1;queue<pair<int, int>> q; q.push(make_pair(0,0));vector<vector<bool>> vis(row, vector<bool>(col,false));vis[0][0] = true;int step = 0;while(!q.empty()){step += 1;for(int size = 0; size < q.size(); size++){pair<int,int> f = q.front();q.pop();if(f.first == (row-1) && f.second == (col-1)) return step;for(int i = -1; i <= 1; i++){for(int j = -1; j <= 1; j++){int newX = f.first + i;int newY = f.second + j;if(newX<0 || newY < 0 || newX >= row || newY >= col || vis[newX][newY] == true || grid[newX][newY] == 1) continue;else {q.push(make_pair(newX, newY));vis[newX][newY] = true;}}}}}return -1;}};

?

總結(jié)

以上是生活随笔為你收集整理的leetcode -- 1091. 二进制矩阵中的最短路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。