Giả sử chúng ta có một lưới. Có ít ký hiệu. "." là cho biết ô trống, "#" là tường, "@" là điểm bắt đầu, ("a", "b", ...) tất cả đều là khóa và ("A", "B", ... ) tất cả đều là ổ khóa. Chúng ta sẽ bắt đầu từ điểm xuất phát và một bước di chuyển bao gồm đi bộ một khoảng trống theo một trong 4 hướng (trái, phải, trên, dưới). Chúng tôi sẽ không đi ra ngoài lưới điện, và có những bức tường chắn đường chúng tôi. Nếu chúng ta đi qua một chiếc chìa khóa, chúng ta sẽ nhặt nó lên. Chúng tôi không thể đi qua ổ khóa trừ khi chúng tôi có chìa khóa tương ứng.
Đối với mỗi ổ khóa như A, B, v.v. chúng ta có các khóa như a, b, v.v., vì vậy các ổ khóa có cùng ký tự viết hoa và các khóa giống nhau với các ký tự viết thường.
Chúng ta phải tìm ra số lần di chuyển thấp nhất để có được tất cả các phím. Nếu không thể, hãy trả về -1.
Vì vậy, nếu đầu vào là ["@ .a. #", "###. #", "B.A.B"], thì đầu ra sẽ là 8
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=số hàng, m:=số cột
-
Xác định kích thước bắt đầu của mảng là 3
-
cnt:=0
-
để khởi tạo i:=0, khi i
-
để khởi tạo j:=0, khi j
-
nếu lưới [i, j] giống với '@', thì -
-
start [1]:=i, start [2]:=j
-
-
nếu lưới [i, j]> ='a' và lưới [i, j] <='f', thì -
-
cnt:=tối đa của cnt và lưới [i, j] - 'a' + 1
-
-
-
-
Xác định một tập hợp đã truy cập
-
yêu cầu:=2 ^ (cnt - 1)
-
Xác định một hàng đợi q của mảng
-
chèn start vào q
-
chèn bắt đầu vào đã truy cập
-
cấp:=0
-
while (không phải q trống), do -
-
sz:=kích thước của q
-
trong khi sz khác 0, giảm sz sau mỗi lần lặp, thực hiện -
-
Xác định một mảng curr:=phần tử phía trước của q
-
xóa phần tử khỏi q
-
phím:=curr [0]
-
nếu khóa giống với yêu cầu, thì -
-
mức trả lại
-
-
x:=curr [1], y:=curr [2]
-
presKey:=key
-
để 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]
-
key:=presKey
-
nếu nx> =0 và ny> =0 và nx
-
nếu lưới [nx, ny] giống với '#', thì -
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
nếu grid [nx, ny]> ='a' và grid [nx, ny] <='f', thì -
-
key:=key OR (2 ^ (grid [nx, ny] - ASCII of 'a'))
-
-
nếu grid [nx, ny]> ='A' và grid [nx, ny] <='F', thì -
-
nếu (phím shift sang phải (lưới [nx, ny] - ASCII của 'A') timesAND 1) bằng 0, thì -
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
-
Xác định trạng thái mảng ({key, nx, ny})
-
nếu trạng thái là được truy cập, thì -
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
chèn trạng thái vào q
-
chèn trạng thái vào đã thăm
-
-
-
-
(tăng cấp 1)
-
-
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}};
class Solution {
public:
int shortestPathAllKeys(vector<string>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<int> start(3);
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '@') {
start[1] = i;
start[2] = j;
}
if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
cnt = max(cnt, grid[i][j] - 'a' + 1);
}
}
}
set<vector<int> > visited;
int req = (1 << cnt) - 1;
queue<vector<int> > q;
q.push(start);
visited.insert(start);
int level = 0;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
vector<int> curr = q.front();
q.pop();
int key = curr[0];
if (key == req)
return level;
int x = curr[1];
int y = curr[2];
int nx, ny;
int prevKey = key;
for (int i = 0; i < 4; i++) {
nx = x + dir[i][0];
ny = y + dir[i][1];
key = prevKey;
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (grid[nx][ny] == '#')
continue;
if (grid[nx][ny] >= 'a' && grid[nx][ny] <=
'f') {
key |= (1 << (grid[nx][ny] - 'a'));
}
if (grid[nx][ny] >= 'A' && grid[nx][ny] <=
'F') {
if (((key >> (grid[nx][ny] - 'A')) & 1)
== 0)
continue;
}
vector<int> state({ key, nx, ny });
if (visited.count(state))
continue;
q.push(state);
visited.insert(state);
}
}
}
level++;
}
return -1;
}
};
main(){
Solution ob;
vector<string> v = {"@.a.#","###.#","b.A.B"};
cout << (ob.shortestPathAllKeys(v));
} Đầu vào
{"@.a.#","###.#","b.A.B"} Đầu ra
8