資料結構
網路
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 次瀏覽
