Giả sử có một mê cung với không gian trống và tường và cũng có một quả bóng trong mê cung đó. Quả bóng có thể đi qua khoảng không bằng cách lăn lên (u), xuống (d), trái (l) hoặc phải (r), nhưng nó vẫn tiếp tục lăn cho đến khi va vào tường. Khi quả bóng dừng lại, nó có thể chọn hướng tiếp theo. Một lỗ hổng cũng nằm trong mê cung đó. Quả bóng sẽ rơi vào lỗ nếu nó lăn tới lỗ.
Vì vậy, nếu chúng ta có vị trí quả bóng, vị trí lỗ và mê cung, chúng ta phải tìm cách làm thế nào để quả bóng có thể rơi vào lỗ bằng cách di chuyển một khoảng cách ngắn nhất. Ở đây khoảng cách được xác định bằng số khoảng trống mà bóng di chuyển từ đầu (không bao gồm) đến lỗ (bao gồm).
Trả lại hướng di chuyển bằng cách sử dụng 'u', 'd', 'l' và 'r'. Vì có thể có một số cách ngắn nhất khác nhau, Và kết quả đầu ra phải là cách nhỏ nhất về mặt từ vựng. Nếu bóng không thể đến lỗ, hiển thị "không thể".
Ở đây mê cung được biểu diễn bằng một ma trận nhị phân. 1 có nghĩa là bức tường và 0 có nghĩa là không gian trống. Tọa độ bóng và lỗ được thể hiện bằng chỉ số hàng và cột.
Vì vậy, nếu đầu vào giống như
Sau đó, đầu ra sẽ là ‘lul’ khi di chuyển sang trái, sau đó lên rồi sang trái, một kết quả khác có thể là ‘ul’, lên rồi sang trái, cả hai đều có độ dài 6, nhưng về mặt từ vựng không nhỏ hơn ‘lul’
Để 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 kiểu dữ liệu được gọi là Dữ liệu, kiểu này sẽ bao gồm khoảng cách, một chuỗi d và tọa độ x, y.
-
Xác định kích thước mảng:4 x 2:={{1, 0}, {0, - 1}, {0, 1}, {- 1, 0}}
-
Xác định kích thước mảng:4:={'d', 'l', 'r', 'u'}
-
Xác định một hàm ok (), điều này sẽ nhận x1, y1, x2, y2,
-
trả về true nếu x1 giống x2 VÀ y1 giống y2
-
Từ phương thức chính, hãy làm như sau -
-
n:=kích thước hàng của mê cung
-
m:=(nếu n khác 0 thì kích thước col của mê cung, ngược lại là 0)
-
Xác định một hàng đợi ưu tiên pq
-
chèn dữ liệu mới với (0, ball [0], ball [1], "") vào pq
-
Xác định một mảng 2D được truy cập có kích thước n x m
-
while (không phải pq trống), do -
-
curr:=phần tử trên cùng của pq
-
x:=curr.x
-
y:=curr.y
-
dist:=curr.dist
-
d:=curr.d
-
nếu ok (x, y, lỗ [0], lỗ [1]), thì -
-
trở lại d
-
-
đã ghé thăm [x, y]:=true
-
xóa phần tử khỏi pq
-
để khởi tạo k:=0, khi k - 4, cập nhật (tăng k lên 1), thực hiện -
-
nx:=x, ny:=y
-
tempDist:=0
-
while nx + dir [k, 0]
=0 and ny + dir [k, 1] =0 and maze [nx + dir [k, 0], ny + dir [k, 1]] là 0, do - -
nx:=nx + dir [k, 0]
-
ny:=ny + dir [k, 1]
-
(tăng tempDist lên 1)
-
nếu đồng ý (nx, ny, lỗ [0], lỗ [1]), thì -
-
Ra khỏi vòng lặp
-
-
-
nếu lượt truy cập [nx, ny] bằng 0 thì -
-
chèn Dữ liệu mới (dist + tempDist, nx, ny, d + dirst [k]) vào pq
-
-
-
trả về "không thể"
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char dirst[4] = {'d', 'l', 'r', 'u'};
class Solution {
public:
struct Data {
int dist;
string d;
int x, y;
Data(int a, int b, int c, string s) {
d = s;
dist = a;
x = b;
y = c;
}
};
struct Comparator {
bool operator()(Data a, Data b) {
return a.dist != b.dist ? !(a.dist < b.dist) : !(a.d < b.d);
}
};
bool ok(int x1, int y1, int x2, int y2) { return x1 == x2 && y1 == y2; }
string findShortestWay(vector<vector<int>> &maze, vector<int>&ball,
vector<int> &hole) {
int n = maze.size();
int m = n ? maze[0].size() : 0;
priority_queue<vector<Data>, vector<Data>, Comparator> pq;
pq.push(Data(0, ball[0], ball[1], ""));
vector<vector<bool>> visited(n, vector<bool>(m));
while (!pq.empty()) {
Data curr = pq.top();
int x = curr.x;
int y = curr.y;
int dist = curr.dist;
string d = curr.d;
if (ok(x, y, hole[0], hole[1])) {
return d;
}
visited[x][y] = true;
pq.pop();
for (int k = 0; k < 4; k++) {
int nx = x;
int ny = y;
int tempDist = 0;
while (nx + dir[k][0] < n && nx + dir[k][0] >= 0 && ny + dir[k][1] < m && ny + dir[k][1] >= 0 && !maze[nx + dir[k][0]][ny + dir[k][1]]) {
nx += dir[k][0];
ny += dir[k][1];
tempDist++;
if (ok(nx, ny, hole[0], hole[1]))
break;
}
if (!visited[nx][ny]) {
pq.push(Data(dist + tempDist, nx, ny, d + dirst[k]));
}
}
}
return "impossible";
}
};
main() {
Solution ob;
vector<vector<int>> v = {
{0, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 0}};
vector<int> v1 = {4, 3}, v2 = {0, 1};
cout << (ob.findShortestWay(v, v1, v2));
} Đầu vào
vector<vector<int>> v = {{0, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 0}};
vector<int> v1 = {4, 3}, v2 = {0, 1}; Đầu ra
lul