数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究带有障碍物消除的网格中求最短路径（C++）
假设我们有一个 m x n 的网格，其中每个单元格的值为 0 或 1。0 表示空单元格，1 表示被阻塞的单元格。一步内，我们可以从一个空单元格移动到相邻的（上、下、左、右）空单元格。给定最多可以消除 k 个障碍物，我们必须找到从左上角单元格 (0, 0) 到右下角单元格 (m-1, n-1) 的最小步数。如果没有这样的路径，则返回 -1。
例如，如果输入如下：
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
并且 k 为 1，则输出为 6，因为不消除任何障碍物的最短路径为 10。在 (3,2) 位置消除一个障碍物后的最短路径为 6。该路径为 (0,0) 到 (0,1) 到 (0,2) 到 (1,2) 到 (2,2) 到 (3,2) 到 (4,2)。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 ok()，用于检查 x 和 y 是否在范围 r 和 c 内。
定义一个大小为 50 x 50 x 2000 的数组 dp。
定义一个数据结构，其中包含 x、y、k 和长度。
在主方法中执行以下操作：
用无穷大填充 dp。
r := 行数，c := 列数。
定义一个队列 q。
创建一个名为 root 的数据对象，其中 (x = 0, y = 0, k, length = 0)。
将 root 插入 q。
当 (q 不为空) 时，执行以下操作：
node := q 的第一个元素。
从 q 中删除该元素。
x := node.x，y := node.y，k := node.k，length := node.length。
如果 x 等于 r - 1 且 y 等于 c - 1，则：
返回 length。
(将 length 加 1)
初始化 i := 0，当 i < 4 时，更新 (i 加 1)，执行以下操作：
nx := x + dir[i, 0]
ny := y + dir[i, 1]
如果 nx 等于 r - 1 且 ny 等于 c - 1，则：
返回 length。
如果 ok(nx, ny, r, c) 为真，则：
如果 grid[nx, ny] 等于 0，则：
如果 length < dp[nx, ny, k]，则：
将包含 (x = nx, y = ny, k, length) 的新数据对象插入 q。
dp[nx, ny, k] := length。
否则
如果 k > 0 且 length < dp[nx, ny, k]，则：
将包含 (x = nx, y = ny, k = k - 1, length) 的新数据对象插入 q。
dp[nx, ny, k] := length。
返回 -1。
让我们看看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
int dir [4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dp[50][50][2000];
struct Data{
int x, y, k, length;
Data(int a, int b, int c, int d){
x = a;
y = b;
k = c;
length = d;
}
};
class Solution {
public:
void pre(){
for (int i = 0; i < 50; i++) {
for (int j = 0; j < 50; j++) {
for (int k = 0; k < 2000; k++) {
dp[i][j][k] = INT_MAX;
}
}
}
}
bool ok(int x, int y, int r, int c){
return (x < r && y < c && x >= 0 && y >= 0);
}
int shortestPath(vector<vector<int> >& grid, int k){
pre();
int r = grid.size();
int c = grid[0].size();
queue<Data> q;
Data root(0, 0, k, 0);
q.push(root);
while (!q.empty()) {
Data node = q.front();
q.pop();
int x = node.x;
int y = node.y;
int k = node.k;
int length = node.length;
if (x == r - 1 && y == c - 1)
return length;
length++;
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx == r - 1 && ny == c - 1)
return length;
if (ok(nx, ny, r, c)) {
if (grid[nx][ny] == 0) {
if (length < dp[nx][ny][k]) {
q.push(Data(nx, ny, k, length));
dp[nx][ny][k] = length;
}
}
else {
if (k > 0 && length < dp[nx][ny][k]) {
q.push(Data(nx, ny, k - 1, length));
dp[nx][ny][k] = length;
}
}
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,0,0},{1,1,0},{0,0,0},{0,1,1},
{0,0,0}};
cout << (ob.shortestPath(v, 1));
}输入
{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}输出
6
浏览量：507
