数据结构
网络
关系数据库管理系统 (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 次浏览
广告