数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究矩阵中两点之间最多经过 K 个障碍物的最短路径
在本文中，我们将找到矩阵中两点之间的最短路径。矩阵包含两种类型的单元格，空单元格和包含障碍物的单元格。我们给定一个整数 K，表示我们最多可以移除 K 个障碍物以到达目的地。
在本文中讨论的方法中，我们将对矩阵进行广度优先搜索 (BFS) 以找到最短路径。我们将使用队列数据结构，它将存储整数向量。该向量将包含 3 个整数，x 坐标、y 坐标以及在该特定路径上可以移除的障碍物数量。我们还将使用另一个矩阵，它将存储到达原始矩阵中某个单元格后可以移除的当前最大障碍物数量。
问题陈述
我们给定一个大小为 N*M 的矩阵和一个整数 K。该矩阵由两种类型的单元格组成，由 0 表示的空单元格和由 1 表示的障碍物。我们需要找到从 (0,0) 到 (N-1, M-1) 的最短路径，前提是我们最多只能移除 K 个障碍物。
在一次移动中，我们可以从当前单元格向上、向下、向左和向右移动。
我们不能离开矩阵的边界。
示例
输入
arr =
{
{0,1}
{1,1}
}
k=1
输出
-1
解释
我们将从起始索引转到 {0,1} 或 {1,0}。转到其中任何一个位置，我们需要移除一个障碍物。
现在，我们需要转到 {1,1}，但要做到这一点，我们需要移除该单元格上的障碍物，这是不可能的，因为我们已经移除了一个障碍物。
所以，输出将是 –1。
输入
arr =
{
{0,1}
{1,1}
}
k=2
输出
2
解释
我们将从起始索引转到 {0,1} 或 {1,0}。转到其中任何一个位置，我们需要移除一个障碍物。
现在，我们需要转到 {1,1}，但要做到这一点，我们需要移除该单元格上的障碍物，这现在成为可能，因为我们可以移除两个障碍物。
所以，输出将是 2。
输入
arr =
{
{0,1,0}
{1,1,1}
}
k=2
输出
3
解释
最短路径如下：
{0,0} -> {0,1} -> {0,2} -> {1,2}
并且我们只需要在这条路径上移除 2 个障碍物。
因此，答案是 3。
方法
在这种方法中，我们将对矩阵进行广度优先搜索 (BFS) 以找到最短路径。我们将使用队列数据结构，它将存储整数向量。该向量将包含 3 个整数，x 坐标、y 坐标以及在该特定路径上可以移除的障碍物数量。我们还将使用另一个矩阵，它将存储到达原始矩阵中某个单元格后可以移除的当前最大障碍物数量。我们将创建一个 while 循环，该循环将迭代直到队列为空。在每次迭代中，我们将检查四个方向（上、下、左、右），并查看它们是否在之前被访问过，或者当前的 K 是否大于过去访问它们时的 K。根据情况，我们将把它们推入队列并继续前进。我们将迭代直到找到结束单元格或队列为空。
算法
步骤 1 − 初始化一个队列数据结构，它将存储整数向量。
步骤 1.1 −初始化一个大小为 N*M 的矩阵，mn_k。
步骤 2 − 检查起点和终点是否有障碍物，如果有，则移除这些障碍物并相应地更新 K。
步骤 3 − 将包含 {0,0,K} 的向量添加到队列中。
步骤 4 − 循环直到队列为空
步骤 4.1 − 在一个变量 sz 中获取队列的当前大小。
步骤 4.2 − 从 0 循环到 sz-1。
步骤 4.2.1 − 从队列中获取顶部元素并弹出队列。
步骤 4.2.2 − 如果元素是 (N-1, M-1)，则返回结果。
步骤 4.2.3 − 否则，检查元素的四个方向，上、下、左、右。对于每个方向，检查我们是否有有效的单元格，以及该单元格是否在之前被访问过。如果该单元格之前没有被访问过，或者它已被访问但 K 值较小，则将其添加到队列中并更新矩阵 mn_k。
步骤 4.2.4 − 将结果增加 1。
步骤 5 − 如果队列为空并且我们退出 while 循环，则返回 –1。
示例
#include <bits/stdc++.h>
using namespace std;
int Shortest_Path(vector<vector<int>> &arr,int k){
int dist = 0;
int n = arr.size() , m=arr[0].size();
if(arr[0][0]==1){k--;arr[0][0]=0;}
if(arr[n-1][m-1]==1){k--;arr[n-1][m-1]=0;}
vector<vector<int>> mn_k(n,vector<int>(m,-1));
queue<vector<int>> que;
que.push({0,0,k});
while(!que.empty()){
int sz = que.size();
for(int i=0;i<sz;i++){
vector<int> t = que.front();que.pop();
if(t[0]==(n-1) && t[1]==(m-1))return dist;
if(t[0]>0){
int ck = t[2];
if(arr[t[0]-1][t[1]]==1)t[2]--;
if(t[2]>=0 && mn_k[t[0]-1][t[1]]<t[2]){
mn_k[t[0]-1][t[1]] = t[2];
t[0]--;
que.push(t);
t[0]++;
}
t[2] = ck;
}
if(t[0]<(n-1)){
int ck = t[2];
if(arr[t[0]+1][t[1]]==1)t[2]--;
if(t[2]>=0 && mn_k[t[0]+1][t[1]]<t[2]){
mn_k[t[0]+1][t[1]] = t[2];
t[0]++;
que.push(t);
t[0]--;
}
t[2] = ck;
}
if(t[1]>0){
int ck = t[2];
if(arr[t[0]][t[1]-1]==1)t[2]--;
if(t[2]>=0 && mn_k[t[0]][t[1]-1]<t[2]){
mn_k[t[0]][t[1]-1] = t[2];
t[1]--;
que.push(t);
t[1]++;
}
t[2] = ck;
}
if(t[1]<(m-1)){
int ck = t[2];
if(arr[t[0]][t[1]+1]==1)t[2]--;
if(t[2]>=0 && mn_k[t[0]][t[1]+1]<t[2]){
mn_k[t[0]][t[1]+1] = t[2];
t[1]++;
que.push(t);
t[1]--;
}
t[2] = ck;
}
}
dist++;
}
return -1;
}
int main(){
vector<vector<int>> arr = {
{0,1,0},
{1,1,1}
};
int k = 2;
cout<<Shortest_Path(arr,k)<<endl;
return 0;
}
输出
3
时间复杂度 − O(N*M*K)，其中 N 是行数，M 是列数，K 是我们可以移除的障碍物数量
空间复杂度 − O(N*M*K)
138 次浏览
