假设我们有amxn网格，这里每个单元格为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和长度。
从主要方法中执行以下操作-
用inf填充dp
r：=行数，c：=列数
定义一个队列q
使用（x = 0，y = 0，k，length = 0）创建名为root的数据对象
将根插入q
当（不是q为空）时，执行-
nx：= x + dir [i，0]
ny：= y + dir [i，1]
如果nx与r-1相同，ny与c-1相同，则-
如果ok(nx,ny,r,c)为真，则-
返回长度
如果k> 0且长度<dp [nx，ny，k]，则-
将具有（x = nx，y = ny，k = k-1，长度）的新数据对象插入q
dp [nx，ny，k]：=长度
如果长度<dp [nx，ny，k]，则-
将（x = nx，y = ny，k，长度）的新数据对象插入q
dp [nx，ny，k]：=长度
如果grid [nx，ny]与0相同，则-
除此以外
返回长度
节点：= q的第一个元素
从q删除元素
x：= node.x，y：= node.y，k：= node.k，长度：= node.length
如果x与r-1相同且y与c-1相同，则-
（长度增加1）
对于初始化i：= 0，当i <4时，更新（将i增加1），请执行-
返回-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