資料結構
網路
關係資料庫管理系統 (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
