Giả sử chúng ta có một lưới m x n, ở đây mỗi ô là 0 hoặc 1. 0 ô trống và 1 ô bị chặn. Trong một bước, chúng ta có thể di chuyển lên, xuống, sang trái hoặc sang phải từ và đến một ô trống. Chúng ta phải tìm số bước tối thiểu để đi từ ô góc trên bên trái (0, 0) đến ô góc dưới bên phải (m-1, n-1) cho rằng chúng ta có thể loại bỏ nhiều nhất k chướng ngại vật. Nếu không có cách nào như vậy, hãy trả về -1.
Vì vậy, nếu đầu vào giống như
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
và k là 1, thì đầu ra sẽ là 6, vì con đường ngắn nhất mà không loại bỏ bất kỳ chướng ngại vật nào là 10. Con đường ngắn nhất với một loại bỏ chướng ngại vật ở vị trí (3,2) sẽ là 6. Con đường như vậy sẽ là (0,0) đến (0,1) đến (0,2) đến (1,2) đến (2,2) đến (3,2) đến (4,2).
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm ok (), điều này sẽ kiểm tra xem x và y có nằm trong phạm vi r và c hay không
-
Xác định một mảng dp có kích thước 50 x 50 x 2000
-
Xác định một cấu trúc Dữ liệu có x, y, k và độ dài.
-
Từ phương thức chính, thực hiện như sau -
-
Điền vào dp với inf
-
r:=số hàng, c:=số cột
-
Xác định một hàng đợi q
-
Tạo đối tượng Dữ liệu được gọi là root với (x =0, y =0, k, length =0)
-
chèn root vào q
-
while (không phải q trống), do -
-
node:=phần tử đầu tiên của q
-
xóa phần tử khỏi q
-
x:=node.x, y:=node.y, k:=node.k, length:=node.length
-
nếu x giống với r - 1 và y giống với c - 1, thì -
-
chiều dài trả về
-
-
(tăng chiều dài lên 1)
-
để khởi tạo i:=0, khi i <4, cập nhật (tăng i lên 1), thực hiện -
-
nx:=x + dir [i, 0]
-
ny:=y + dir [i, 1]
-
nếu nx giống với r - 1 và ny giống với c - 1, thì -
-
chiều dài trả về
-
-
nếu ok (nx, ny, r, c) là true thì -
-
nếu lưới [nx, ny] giống 0 thì -
-
nếu chiều dài
-
chèn đối tượng dữ liệu mới với (x =nx, y =ny, k, length) vào q
-
dp [nx, ny, k]:=length
-
-
-
Nếu không
-
nếu k> 0 và chiều dài
-
chèn đối tượng dữ liệu mới với (x =nx, y =ny, k =k - 1, length) vào q
-
dp [nx, ny, k]:=length
-
-
-
-
-
-
trả về -1
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}} Đầu ra
6