資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++實現二進位制矩陣中的最短路徑
假設我們有一個N x N的方格網，其中每個單元格要麼為空(0)，要麼被阻塞(1)。從左上角到右下角的清晰路徑長度為k，當且僅當它由單元格C_1, C_2, ..., C_k組成，其中：
相鄰單元格C_i和C_{i+1}是8方向連線的（因此它們不同且共享一條邊或角）
C_1位於(0, 0)位置
C_k位於(N-1, N-1)位置
如果C_i位於(r, c)，則grid[r, c]為空或包含0
我們必須找到從左上角到右下角的最短清晰路徑的長度。如果沒有這樣的路徑，則返回-1。
例如，如果網格如下：
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 1 | 0 |
橙色單元格將構成路徑。長度為4
為了解決這個問題，我們將遵循以下步驟：
定義一個方向陣列，它將儲存8對移動8個不同方向的值。因此該陣列類似於[[1,1], [1,-1], [-1,1], [1,0], [0,1], [-1,-1], [0,-1], [-1,0]]
主要部分將以網格作為輸入，其作用如下：
定義一個點佇列q，n:=行數
如果grid[0, 0]為0，則建立一個新點p(0, 0, 1)，將p插入q，並將grid[0, 0]設定為1
當q不為空時
curr:=q中的第一個點，從q中刪除第一個點
x:=curr的x值，y:=curr的y值，c:=curr的c值
如果x = n – 1且y = n – 1，則返回c
將c加1
對於範圍0到7中的i
X := x + d[i, 0], Y := y + d[i, 1]
如果X在0和n之間，並且y在0和n之間，並且grid[X, Y]為0，則
grid[X, Y] := 1
將新點p (X, Y, c)插入q
返回-1
讓我們來看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
int d[8][2] = {{1, 1}, {1, -1}, {-1, 1}, {1, 0}, {0, 1}, {-1, -1},
{0, -1}, {-1, 0}};
struct point{
int x, y, c;
point(int a, int b, int z){
x = a;
y = b;
c = z;
}
};
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
queue <point> q;
int n = grid.size();
if(!grid[0][0]){
q.push(point(0, 0, 1));
grid[0][0] = 1;
}
while(!q.empty()){
point curr = q.front();
q.pop();
int x = curr.x;
int y = curr.y;
int c = curr.c;
if(x == n-1 && y == n-1)return c;
c++;
for(int i = 0; i < 8; i++){
int X = x + d[i][0];
int Y = y + d[i][1];
if(X >= 0 && X < n && Y >= 0 && Y < n &&
!grid[X][Y]){
grid[X][Y] = 1;
q.push(point(X, Y, c));
}
}
}
return -1;
}
};
main(){
vector<vector<int>> v = {{0,0,0},{1,1,0},{1,1,0}};
Solution ob;
cout << (ob.shortestPathBinaryMatrix(v));
}輸入
[[0,0,0],[1,1,0],[1,1,0]]
輸出
4
更新於：2020年5月2日
742 次瀏覽
廣告