Trò chơi 2: Mê cung trong C++ và Python: sinh mê cung bằng DFS ngẫu nhiên, tìm đường ngắn nhất bằng BFS và truy vết đường đi
Lời mở đầu
Chắc hẳn em từng cầm bút chì dò đường trong mê cung ở trang cuối một cuốn truyện tranh: bắt đầu ở cửa vào, lách qua các bức tường, tìm tới cửa ra. Luật chơi chỉ có vậy, nhưng đằng sau nó là hai câu hỏi rất “tin học”: con đường em tìm được có phải ngắn nhất không, và người ta vẽ mê cung thế nào mà lúc nào cũng có lối ra, không có góc nào bị nhốt kín?
Hình 1. Một mê cung 6 × 6 phòng do máy tính sinh ra. Đường xanh lá là đường ngắn nhất từ S tới E, do BFS tìm.
Cả hai câu hỏi đều được trả lời bằng hai thuật toán em đã gặp ở bài 21: BFS và DFS. Bài 21 đã dạy em loang trên lưới để đếm vùng; hôm nay mình đi xa hơn: dùng DFS ngẫu nhiên để sinh ra mê cung, dùng BFS để tìm đường ngắn nhất và truy vết từng bước đi, rồi nâng cấp mê cung với chìa khoá, cửa, quyền phá tường và quái vật, đúng những biến thể hay gặp trong đề thi HSG. Bài dùng nhiều mảng 2 chiều và mảng hướng dx, dy; nếu chưa vững em xem lại hai bài đó trước nhé. Còn nếu em vừa chơi xong Trò chơi 1: Tháp Hà Nội thì đệ quy và ngăn xếp ở đó sẽ quay lại ngay trong phần 2.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Chơi thử: thoát khỏi mê cung
Khởi động một chút nhé. Em là chấm tím ở ô S, nhiệm vụ là tới ô E. Bấm vào mê cung rồi dùng phím mũi tên (hoặc W, A, S, D), trên điện thoại thì bấm các nút ↑ ← → ↓ hay chạm vào ô kề bên. Máy đếm số bước của em; tới đích rồi thì bấm 🧭 Máy chỉ đường ngắn nhất để so xem em đi thừa bao nhiêu bước. Muốn xem máy “nghĩ” thế nào thì bấm Tiếp ▶ từng bước. Mỗi số mê cung cho ra một mê cung cố định, em có thể rủ bạn cùng chơi một số rồi so điểm.
Mê cung trong máy tính trông thế nào? Trên giấy, mê cung gồm các phòng vuông xếp thành lưới $R \times C$, giữa hai phòng cạnh nhau có thể có một nét tường mỏng. Nét tường mỏng khó lưu, nên ta “phóng to” nó thành ô: dùng lưới ký tự $(2R + 1) \times (2C + 1)$, trong đó
- phòng $(a, b)$ nằm ở ô $(2a + 1,\ 2b + 1)$, tức là ô có hàng lẻ, cột lẻ;
- bức tường giữa phòng $(a, b)$ và phòng bên phải nó nằm ở ô $(2a + 1,\ 2b + 2)$; với phòng bên dưới là ô $(2a + 2,\ 2b + 1)$;
- ô là
#nếu tường còn nguyên, là.nếu tường đã bị đục; hàng 0, cột 0, hàng cuối, cột cuối là viền ngoài, luôn là#.
Hình 2. Cùng một mê cung, bên trái vẽ bằng nét tường mỏng, bên phải là lưới ký tự máy tính lưu. Từ phòng này sang phòng kề là đi 2 ô.
Khi đã là lưới ký tự thì mê cung không khác gì các bài lưới quen thuộc trong đề thi: đề cho $n$, $m$ rồi $n$ dòng, mỗi dòng $m$ ký tự gồm . (ô trống), # (tường), S (xuất phát), E (đích). Từ một ô được đi sang 4 ô chung cạnh. Toàn bộ bài này dùng đúng định dạng đó, và mỗi bước đi là sang một ô (trong trò chơi trên cũng vậy).
int dx[4] = {-1, 0, 1, 0}; // lên, phải, xuống, trái
int dy[4] = {0, 1, 0, -1};
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> g[i]; // đọc cả hàng là một xâu
for(int j = 0; j < m; j++){
if(g[i][j] == 'S'){ sx = i; sy = j; }
if(g[i][j] == 'E'){ ex = i; ey = j; }
}
}string (Python: input() hoặc tách từ sys.stdin) tiện hơn đọc từng ký tự. Thứ tự hướng lên, phải, xuống, trái giữ nguyên trong cả bài, kể cả chữ "URDL" khi in đường đi.Phần 2Sinh mê cung bằng DFS ngẫu nhiên
Một mê cung đẹp cần hai điều: đi được tới mọi phòng (không có phòng bị nhốt kín) và không có vòng (giữa hai phòng chỉ có đúng một đường, nên người chơi phải thật sự “tìm” đường). Mê cung như vậy gọi là mê cung hoàn hảo. Cách sinh nổi tiếng nhất là DFS ngẫu nhiên, hay “thuật toán đào hầm”:
- Bắt đầu với lưới toàn tường. Đứng ở phòng $(0, 0)$, đánh dấu đã thăm, đẩy vào ngăn xếp.
- Nhìn phòng ở đỉnh ngăn xếp. Nếu nó còn phòng kề chưa thăm: chọn ngẫu nhiên một phòng, đục bức tường ở giữa, đánh dấu phòng mới và đẩy nó vào ngăn xếp.
- Nếu mọi phòng kề đều đã thăm (ngõ cụt): lấy phòng đó ra khỏi ngăn xếp, tức là quay lui một bước.
- Lặp lại tới khi ngăn xếp rỗng.
Đây chính là DFS ở bài 21, chỉ khác là thứ tự thử các hướng được xáo ngẫu nhiên, và mỗi lần đi tới phòng mới ta đục bỏ bức tường vừa đi qua. Ngăn xếp đóng vai trò của các lời gọi đệ quy (giống ngăn xếp trong Tháp Hà Nội), nhưng viết bằng vòng lặp thì không lo tràn ngăn xếp khi mê cung lớn. Em bấm Tự chạy để xem đường hầm đào sâu mãi rồi quay lui khi bị vây kín:
Vì sao mê cung luôn hoàn hảo? Mỗi lần đục tường, ta nối thêm một phòng chưa thăm vào khối phòng đã thông với $(0, 0)$. Có $R \cdot C$ phòng, phòng đầu có sẵn, nên đục đúng $R \cdot C - 1$ bức tường thì mọi phòng đều thông nhau. Một khối liền gồm $V$ đỉnh mà chỉ có $V - 1$ cạnh thì không thể có vòng: nó là một cây. Mê cung hoàn hảo chính là một cây khung của lưới phòng (em sẽ gặp lại khái niệm này ở bài 30: DSU và cây khung).
| Bước | Ngăn xếp (đỉnh ở cuối) | Phòng kề chưa thăm | Việc làm |
|---|---|---|---|
| 1 | (0,0) | phải, xuống | chọn ngẫu nhiên “xuống”, đục tường, đẩy (1,0) |
| 2 | (0,0) (1,0) | phải | đục tường, đẩy (1,1) |
| 3 | (0,0) (1,0) (1,1) | lên | đục tường, đẩy (0,1) |
| 4 | (0,0) (1,0) (1,1) (0,1) | (không còn) | ngõ cụt, lấy (0,1) ra |
| 5 | (0,0) (1,0) (1,1) | (không còn) | lấy (1,1) ra |
| … | … | … | ngăn xếp rỗng: xong, đục 3 tường |
Bảng 1. Sinh mê cung 2 × 2 phòng. Bốn phòng, đục đúng 3 bức tường; bức tường giữa (0,0) và (0,1) còn nguyên nên không có vòng.
Ngẫu nhiên mà vẫn chấm bài được? Máy tính không tung xúc xắc thật mà dùng một công thức sinh dãy số trông như ngẫu nhiên. Ở đây mình dùng công thức rất đơn giản $seed \leftarrow seed \cdot 48271 \bmod (2^{31} - 1)$, rồi lấy $seed \bmod cnt$ để chọn một trong $cnt$ hướng. Cùng một seed ban đầu thì luôn ra cùng một dãy số, nên cùng một mê cung. Đó chính là “số mê cung” trong khung chơi thử: em chạy code dưới đây với 8 8 2026 sẽ in ra đúng mê cung mặc định ở phần 1.
Xem code C++ / Python: sinh mê cung hoàn hảo bằng dfs ngẫu nhiên với ngăn xếp (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int R, C;
long long seed;
string g[105];
bool vis[55][55];
int dx[4] = {-1, 0, 1, 0}; // lên, phải, xuống, trái
int dy[4] = {0, 1, 0, -1};
long long nextRand(){ // số giả ngẫu nhiên: cùng seed thì cùng dãy số
seed = seed * 48271 % 2147483647;
return seed;
}
int main(){
cin >> R >> C >> seed;
int n = 2 * R + 1, m = 2 * C + 1;
for(int i = 0; i < n; i++){
g[i] = string(m, '#'); // ban đầu toàn tường
for(int j = 1; j < m; j += 2)
if(i % 2 == 1) g[i][j] = '.'; // phòng: hàng lẻ, cột lẻ
}
vector<pair<int, int>> st; // ngăn xếp các phòng
st.push_back({0, 0});
vis[0][0] = true;
while(!st.empty()){
int x = st.back().first, y = st.back().second; // phòng ở đỉnh ngăn xếp
int cand[4], cnt = 0;
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(nx >= 0 && nx < R && ny >= 0 && ny < C && !vis[nx][ny]) cand[cnt++] = k;
}
if(cnt == 0){ st.pop_back(); continue; } // ngõ cụt: quay lui
int k = cand[nextRand() % cnt]; // chọn ngẫu nhiên một hướng
int nx = x + dx[k], ny = y + dy[k];
g[2 * x + 1 + dx[k]][2 * y + 1 + dy[k]] = '.'; // đục bức tường ở giữa
vis[nx][ny] = true;
st.push_back({nx, ny});
}
g[1][1] = 'S';
g[n - 2][m - 2] = 'E';
for(int i = 0; i < n; i++) cout << g[i] << "\n";
return 0;
}R, C, seed = map(int, input().split())
n, m = 2 * R + 1, 2 * C + 1
dx = [-1, 0, 1, 0] # lên, phải, xuống, trái
dy = [0, 1, 0, -1]
g = [['.' if (i % 2 == 1 and j % 2 == 1) else '#' for j in range(m)] for i in range(n)]
vis = [[False] * C for _ in range(R)]
vis[0][0] = True
st = [(0, 0)] # ngăn xếp các phòng
while st:
x, y = st[-1] # phòng ở đỉnh ngăn xếp
cand = [k for k in range(4)
if 0 <= x + dx[k] < R and 0 <= y + dy[k] < C and not vis[x + dx[k]][y + dy[k]]]
if not cand: # ngõ cụt: quay lui
st.pop()
continue
seed = seed * 48271 % 2147483647 # số giả ngẫu nhiên
k = cand[seed % len(cand)] # chọn ngẫu nhiên một hướng
g[2 * x + 1 + dx[k]][2 * y + 1 + dy[k]] = '.' # đục bức tường ở giữa
vis[x + dx[k]][y + dy[k]] = True
st.append((x + dx[k], y + dy[k]))
g[1][1] = 'S'
g[n - 2][m - 2] = 'E'
print('\n'.join(''.join(r) for r in g))2. Viết DFS đệ quy bằng Python. Mê cung $50 \times 50$ phòng có thể khiến đệ quy sâu tới 2500 tầng, vượt giới hạn mặc định 1000 của Python. Dùng ngăn xếp tự quản như code trên là an toàn nhất.
Phần 3BFS tìm đường ngắn nhất và truy vết đường đi
Nhắc lại ý tưởng của BFS (tìm kiếm theo chiều rộng) ở bài 21: tưởng tượng em nhỏ một giọt mực ở ô S, mực loang đều ra mọi phía, mỗi giây lan sang các ô kề. Ô nào bị mực chạm tới ở giây thứ $d$ thì khoảng cách từ S tới nó đúng bằng $d$, vì mực đi mọi ngả cùng lúc nên không ngả nào tới sớm hơn được. Cài đặt bằng hàng đợi:
- Mảng
d[x][y]= $-1$ cho mọi ô (chưa thăm). Gánd[S] = 0, cho S vào hàng đợi. - Lấy ô ở đầu hàng đợi. Với mỗi ô kề trong lưới, không phải tường, chưa thăm: gán
d[kề] = d[ô] + 1và xếp ô kề vào cuối hàng đợi. - Hàng đợi rỗng thì dừng.
d[E]là đáp án; nếu vẫn là $-1$ thì không có đường.
Hàng đợi luôn có dạng: vài ô khoảng cách $d$ ở đầu, rồi các ô khoảng cách $d + 1$ ở cuối. Vì vậy các ô được lấy ra theo đúng thứ tự khoảng cách tăng dần, như những vòng sóng lan ra. Em xem từng bước trên một lưới có nhiều đường vòng (không phải mê cung hoàn hảo), để thấy BFS chọn đúng đường ngắn:
Truy vết: không chỉ biết bao nhiêu bước, mà còn biết đi thế nào. Mảng d chỉ cho độ dài. Muốn in đường đi, lúc gán d[kề] ta ghi thêm ô kề được tới từ đâu. Có hai cách: lưu hẳn ô cha par[kề] = ô, hoặc gọn hơn, lưu hướng pk[kề] = k đã đi. Khi BFS xong, đứng ở E, đọc k = pk[E] thì biết bước cuối là hướng $k$; lùi ngược hướng đó một ô, lại đọc pk… cho tới khi về S. Các chữ ghi được là đường đi từ E về S, nên cuối cùng phải đảo ngược.
| Ô (hàng, cột) | d | pk | Đến bằng hướng | Chữ |
|---|---|---|---|---|
| (2, 3) = E | 5 | 2 | xuống | D |
| (1, 3) | 4 | 1 | phải | R |
| (1, 2) | 3 | 2 | xuống | D |
| (0, 2) | 2 | 1 | phải | R |
| (0, 1) | 1 | 1 | phải | R |
| (0, 0) = S | 0 | – | – | dừng |
Bảng 2. Truy vết trên lưới S..# / .#.. / ...E: đọc từ E về S được DRDRR, đảo ngược thành RRDRD. Đường ngắn nhất dài 5 bước (đi DDRRR cũng 5 bước, nhưng vì thử hướng phải trước hướng xuống nên BFS gặp đường kia trước).
Em bấm Tiếp để xem từng dòng code chạy trên đúng lưới của Bảng 2, chú ý thứ tự các ô vào hàng đợi và lúc truy vết lùi từng bước:
Xem code C++ / Python: bfs tìm đường ngắn nhất và truy vết in đường đi (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string g[1005];
int d[1005][1005], pk[1005][1005]; // d: khoảng cách, pk: hướng đã đi để VÀO ô
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
string DIR = "URDL"; // lên, phải, xuống, trái
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
int sx = 0, sy = 0, ex = 0, ey = 0;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++){
if(g[i][j] == 'S'){ sx = i; sy = j; }
if(g[i][j] == 'E'){ ex = i; ey = j; }
d[i][j] = -1; // -1 nghĩa là chưa thăm
}
}
queue<pair<int, int>> q;
d[sx][sy] = 0;
q.push({sx, sy});
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // ngoài lưới
if(g[nx][ny] == '#' || d[nx][ny] != -1) continue; // tường hoặc đã thăm
d[nx][ny] = d[x][y] + 1;
pk[nx][ny] = k; // nhớ: tới (nx, ny) bằng hướng k
q.push({nx, ny});
}
}
if(d[ex][ey] == -1){ cout << -1; return 0; }
string path = "";
int x = ex, y = ey;
while(x != sx || y != sy){ // truy vết: lần ngược từ E về S
int k = pk[x][y];
path += DIR[k];
x -= dx[k]; y -= dy[k]; // lùi lại đúng 1 bước theo hướng k
}
reverse(path.begin(), path.end());
cout << d[ex][ey] << "\n" << path;
return 0;
}import sys
from collections import deque
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
DIR = "URDL" # lên, phải, xuống, trái
for i in range(n):
if 'S' in g[i]: sx, sy = i, g[i].index('S')
if 'E' in g[i]: ex, ey = i, g[i].index('E')
d = [[-1] * m for _ in range(n)] # -1 nghĩa là chưa thăm
pk = [[0] * m for _ in range(n)] # hướng đã đi để VÀO ô
d[sx][sy] = 0
q = deque([(sx, sy)])
while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if 0 <= nx < n and 0 <= ny < m and g[nx][ny] != '#' and d[nx][ny] == -1:
d[nx][ny] = d[x][y] + 1
pk[nx][ny] = k # nhớ: tới (nx, ny) bằng hướng k
q.append((nx, ny))
if d[ex][ey] == -1:
print(-1)
else:
path = []
x, y = ex, ey
while (x, y) != (sx, sy): # truy vết: lần ngược từ E về S
k = pk[x][y]
path.append(DIR[k])
x, y = x - dx[k], y - dy[k]
print(d[ex][ey])
print(''.join(reversed(path)))d[nx][ny] = d[x][y] + 1 chạy ngay trước push, nên mỗi ô vào hàng đợi đúng một lần và BFS chạy trong $O(n \cdot m)$.Phần 4DFS hay BFS? Và BFS đa nguồn
DFS cũng tìm được đường từ S tới E: cứ lao theo một hướng, gặp ngõ cụt thì quay lui. Vậy sao không dùng DFS cho gọn? Câu trả lời phụ thuộc vào loại mê cung:
- Mê cung hoàn hảo (như ở phần 1, 2): giữa S và E chỉ có đúng một đường không lặp lại ô. DFS tìm được đường nào thì đó cũng là đường ngắn nhất. Ở loại này DFS hay BFS đều đúng.
- Lưới có vòng (hầu hết đề thi): có nhiều đường khác nhau. DFS chỉ trả về đường đầu tiên nó gặp, thường vòng vèo. Chỉ BFS mới đảm bảo ngắn nhất.
Hình 3. Lưới mặc định của mô phỏng ở phần 3. DFS (thử lên, phải, xuống, trái) đi theo hành lang trên cùng và trả về đường dài 14 bước; BFS tìm được đường 12 bước. Số trong ô là thứ tự bước đi.
Em quay lại mô phỏng ở phần 3, chọn DFS (đệ quy) để xem DFS lao vào hành lang trên cùng, quay lui ở ngõ cụt và cuối cùng trả về đường dài hơn hẳn. Tuy vậy, DFS vẫn rất hữu ích ở những việc không cần ngắn nhất:
| Việc cần làm | BFS (hàng đợi) | DFS (đệ quy / ngăn xếp) |
|---|---|---|
| Đường đi ngắn nhất (mỗi bước như nhau) | đúng | sai khi có vòng |
| Có đường từ S tới E không? | được | được |
| Đếm số ô đến được, đếm số vùng | được | được, code ngắn |
| Sinh mê cung hoàn hảo | cho mê cung kém đẹp | đúng sở trường |
| Lưới $1000 \times 1000$ | an toàn | đệ quy sâu $10^6$ tầng dễ tràn ngăn xếp |
Bảng 3. Chọn BFS hay DFS. Khi phân vân, chọn BFS: nó làm được mọi việc DFS làm trên lưới, lại không lo tràn ngăn xếp.
BFS đa nguồn: khi có nhiều điểm xuất phát. Giả sử trong mê cung có vài con quái vật M, và em muốn biết với mỗi ô, quái vật gần nhất cần bao nhiêu bước để tới. Chạy BFS riêng từ từng con rồi lấy min thì quá chậm khi có hàng nghìn con. Mẹo rất đẹp: cho tất cả quái vật vào hàng đợi ngay từ đầu với d = 0, rồi chạy BFS như bình thường. Các làn sóng xuất phát cùng lúc và lan đều, ô nào bị sóng nào chạm trước thì quái vật đó là gần nhất. Tổng thời gian vẫn chỉ $O(n \cdot m)$.
Xem code C++ / Python: bfs đa nguồn: khoảng cách tới quái vật gần nhất (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string g[1005];
int d[1005][1005];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
queue<pair<int, int>> q;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++){
d[i][j] = -1;
if(g[i][j] == 'M'){ d[i][j] = 0; q.push({i, j}); } // MỌI nguồn vào hàng đợi
}
}
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(g[nx][ny] == '#' || d[nx][ny] != -1) continue;
d[nx][ny] = d[x][y] + 1;
q.push({nx, ny});
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(g[i][j] == '#') cout << "# ";
else cout << d[i][j] << " ";
}
cout << "\n";
}
return 0;
}import sys
from collections import deque
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
d = [[-1] * m for _ in range(n)]
q = deque()
for i in range(n):
for j in range(m):
if g[i][j] == 'M': # MỌI nguồn vào hàng đợi
d[i][j] = 0
q.append((i, j))
while q:
x, y = q.popleft()
for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
if 0 <= nx < n and 0 <= ny < m and g[nx][ny] != '#' and d[nx][ny] == -1:
d[nx][ny] = d[x][y] + 1
q.append((nx, ny))
out = []
for i in range(n):
out.append(' '.join('#' if g[i][j] == '#' else str(d[i][j]) for j in range(m)))
print('\n'.join(out))Phần 5Biến thể: chìa khoá, phá tường, ô bùn
Đề thi hiếm khi cho mê cung trần trụi. Thường sẽ có thêm luật: nhặt chìa khoá mới mở được cửa, được phá một bức tường, có ô đi chậm… Bí quyết chung chỉ một câu:
Được phá tối đa 1 bức tường. Trạng thái là $(x, y, b)$ với $b = 0$ nếu chưa phá tường nào, $b = 1$ nếu đã phá. Hãy hình dung hai tầng lưới chồng lên nhau: ở tầng 0, bước vào ô trống thì vẫn ở tầng 0, bước vào ô tường thì rơi xuống tầng 1; ở tầng 1, tường lại là tường. Đáp án là $\min(d[0][E],\ d[1][E])$. Em bấm từng bước để thấy hai tầng cùng lan sóng:
Xem code C++ / Python: bfs hai tầng: được phá tối đa một bức tường (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string g[1005];
int d[2][1005][1005]; // d[b][x][y]: b = số tường đã phá (0 hoặc 1)
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
int sx = 0, sy = 0, ex = 0, ey = 0;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++){
if(g[i][j] == 'S'){ sx = i; sy = j; }
if(g[i][j] == 'E'){ ex = i; ey = j; }
d[0][i][j] = d[1][i][j] = -1;
}
}
queue<array<int, 3>> q; // trạng thái (b, x, y)
d[0][sx][sy] = 0;
q.push({0, sx, sy});
while(!q.empty()){
auto [b, x, y] = q.front();
q.pop();
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
int nb = b;
if(g[nx][ny] == '#'){
if(b == 1) continue; // đã phá rồi, không phá thêm được
nb = 1; // phá bức tường này: xuống tầng 1
}
if(d[nb][nx][ny] != -1) continue;
d[nb][nx][ny] = d[b][x][y] + 1;
q.push({nb, nx, ny});
}
}
int a = d[0][ex][ey], c = d[1][ex][ey];
if(a == -1) cout << c; // c cũng có thể là -1
else if(c == -1) cout << a;
else cout << min(a, c);
return 0;
}import sys
from collections import deque
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
for i in range(n):
if 'S' in g[i]: sx, sy = i, g[i].index('S')
if 'E' in g[i]: ex, ey = i, g[i].index('E')
d = [[[-1] * m for _ in range(n)] for _ in range(2)] # d[b][x][y], b = số tường đã phá
d[0][sx][sy] = 0
q = deque([(0, sx, sy)]) # trạng thái (b, x, y)
while q:
b, x, y = q.popleft()
for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
if not (0 <= nx < n and 0 <= ny < m):
continue
nb = b
if g[nx][ny] == '#':
if b == 1: # đã phá rồi, không phá thêm được
continue
nb = 1 # phá bức tường này: xuống tầng 1
if d[nb][nx][ny] == -1:
d[nb][nx][ny] = d[b][x][y] + 1
q.append((nb, nx, ny))
res = [v for v in (d[0][ex][ey], d[1][ex][ey]) if v != -1]
print(min(res) if res else -1)Được phá tối đa $k$ bức tường thì làm $k + 1$ tầng (bài tập 5). Còn nếu đề hỏi phá ít tường nhất để tới E (đi bao xa cũng được) thì lại là bài khác: đi vào ô trống tốn 0, vào ô tường tốn 1, đó là BFS 0-1 ở bài 29.
Chìa khoá và cửa. Mê cung có tối đa $K$ loại chìa khoá a, b, c… và cửa tương ứng A, B, C… Bước vào ô chìa khoá thì nhặt được (giữ mãi), cửa chỉ đi qua được khi đã có đúng chìa. Thứ cần nhớ là tập chìa đã có, lưu gọn bằng một số $mask$ có $K$ bit (bit $i$ bằng 1 nếu đã có chìa thứ $i$, xem bài 20: thao tác bit). Trạng thái là $(x, y, mask)$, có $n \cdot m \cdot 2^K$ trạng thái.
| Gặp ô | Điều kiện bước vào | Trạng thái mới |
|---|---|---|
., S, E | luôn được | $(x', y', mask)$ |
chìa khoá c | luôn được | $(x', y', mask \mid 2^{c - 'a'})$ |
cửa C | bit $C - 'A'$ của $mask$ bằng 1 | $(x', y', mask)$ |
# | không bao giờ | – |
Bảng 4. Luật chuyển trạng thái trong mê cung có chìa khoá. Với $K = 4$ loại chìa và lưới $50 \times 50$: $2500 \cdot 16 = 40\,000$ trạng thái, BFS chạy rất nhanh (bài tập 7).
Ô bùn tốn nhiều bước hơn. Giả sử bước vào ô bùn ~ mất 3 giây thay vì 1. Lúc này BFS sai, vì sóng không còn lan đều: BFS chỉ đếm số ô đi qua, không đếm thời gian. Ví dụ lưới 2 hàng S~~E / ....: BFS thấy đi thẳng qua 2 ô bùn chỉ có 3 bước, nhưng mất $3 + 3 + 1 = 7$ giây; đường vòng xuống hàng dưới dài 5 bước mà chỉ mất 5 giây. Mỗi bước có “giá” khác nhau thì phải dùng Dijkstra ở bài 29 (bài tập 6).
- Covid (ICTU P58) (Trung bình)
- Nhà Từ Thiện Swyrin (Trung bình)
- The Time When the Network Becomes Idle (LeetCode 2039) (Trung bình)
- Bin Laden (Khá)
- Hội Chợ (Khó)
- Dịch chuyển tức thời (Khó)
Bài tậpLuyện BFS, DFS trên mê cung
Mê cung $n \times m$ ($1 \le n, m \le 1000$) gồm ô trống ., tường # và đúng một ô S. Từ một ô được đi sang 4 ô chung cạnh. Hỏi từ S đi được tới bao nhiêu ô (tính cả ô S)?
4 5
S..#.
.#.#.
.#.#.
##.#.8📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string g[1005];
bool vis[1005][1005];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
queue<pair<int, int>> q;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++)
if(g[i][j] == 'S'){ vis[i][j] = true; q.push({i, j}); }
}
int cnt = 0;
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
cnt++; // mỗi ô lấy ra là một ô đến được
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(g[nx][ny] == '#' || vis[nx][ny]) continue;
vis[nx][ny] = true;
q.push({nx, ny});
}
}
cout << cnt;
return 0;
}import sys
from collections import deque
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
vis = [[False] * m for _ in range(n)]
q = deque()
for i in range(n):
if 'S' in g[i]:
j = g[i].index('S')
vis[i][j] = True
q.append((i, j))
cnt = 0
while q:
x, y = q.popleft()
cnt += 1 # mỗi ô lấy ra là một ô đến được
for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
if 0 <= nx < n and 0 <= ny < m and g[nx][ny] != '#' and not vis[nx][ny]:
vis[nx][ny] = True
q.append((nx, ny))
print(cnt)Như mê cung ở phần 3 ($1 \le n, m \le 1000$, có đúng một S và một E), nhưng nhân vật đi như quân vua trong cờ vua: mỗi bước sang một trong 8 ô xung quanh (kể cả đường chéo), miễn ô đó trong lưới và không phải tường. In số bước ít nhất từ S tới E, hoặc $-1$ nếu không tới được.
4 4
S#..
.#.#
#.#.
...E4📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
dx, dy của chuyên đề 4. Mỗi bước vẫn tốn 1 nên BFS vẫn cho đường ngắn nhất. Ví dụ: (0,0) → (1,0) → (2,1) → (3,2) → (3,3), đi chéo hai lần để lách qua tường.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string g[1005];
int d[1005][1005];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; // 8 hướng như quân vua
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
queue<pair<int, int>> q;
int ex = 0, ey = 0;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++){
d[i][j] = -1;
if(g[i][j] == 'E'){ ex = i; ey = j; }
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(g[i][j] == 'S'){ d[i][j] = 0; q.push({i, j}); }
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
for(int k = 0; k < 8; k++){
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(g[nx][ny] == '#' || d[nx][ny] != -1) continue;
d[nx][ny] = d[x][y] + 1;
q.push({nx, ny});
}
}
cout << d[ex][ey];
return 0;
}import sys
from collections import deque
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
D8 = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)] # 8 hướng
d = [[-1] * m for _ in range(n)]
q = deque()
for i in range(n):
for j in range(m):
if g[i][j] == 'S':
d[i][j] = 0
q.append((i, j))
elif g[i][j] == 'E':
ex, ey = i, j
while q:
x, y = q.popleft()
for ax, ay in D8:
nx, ny = x + ax, y + ay
if 0 <= nx < n and 0 <= ny < m and g[nx][ny] != '#' and d[nx][ny] == -1:
d[nx][ny] = d[x][y] + 1
q.append((nx, ny))
print(d[ex][ey])Mê cung $n \times m$ ($1 \le n, m \le 1000$) gồm ., # và đúng một S. Bên ngoài lưới là tự do. Mỗi bước đi sang một ô chung cạnh; từ một ô trống ở biên lưới, bước thêm một bước ra ngoài là thoát. In số bước ít nhất để thoát ra ngoài, hoặc $-1$ nếu bị nhốt.
4 5
#####
#S..#
#.#..
###.#5📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string g[1005];
int d[1005][1005];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
queue<pair<int, int>> q;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++){
d[i][j] = -1;
if(g[i][j] == 'S'){ d[i][j] = 0; q.push({i, j}); }
}
}
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
if(x == 0 || x == n - 1 || y == 0 || y == m - 1){ // ô biên: bước thêm 1 là ra ngoài
cout << d[x][y] + 1;
return 0;
}
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(g[nx][ny] == '#' || d[nx][ny] != -1) continue; // ô kề chắc chắn trong lưới
d[nx][ny] = d[x][y] + 1;
q.push({nx, ny});
}
}
cout << -1;
return 0;
}import sys
from collections import deque
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
d = [[-1] * m for _ in range(n)]
q = deque()
for i in range(n):
if 'S' in g[i]:
j = g[i].index('S')
d[i][j] = 0
q.append((i, j))
ans = -1
while q:
x, y = q.popleft()
if x == 0 or x == n - 1 or y == 0 or y == m - 1: # ô biên: bước thêm 1 là ra ngoài
ans = d[x][y] + 1
break
for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
if g[nx][ny] != '#' and d[nx][ny] == -1: # ô kề chắc chắn trong lưới
d[nx][ny] = d[x][y] + 1
q.append((nx, ny))
print(ans)Cho mê cung hoàn hảo dạng lưới ký tự như phần 2: $n, m$ lẻ, $3 \le n, m \le 1001$, viền ngoài toàn tường, có một S và một E (không nhất thiết ở hai góc), đề bảo đảm giữa hai ô trống bất kỳ có đúng một đường đi không lặp ô. Dòng đầu in độ dài đường đi từ S tới E; sau đó in lại mê cung, trong đó mọi ô trên đường đi (trừ S và E) đổi thành *.
7 7
#######
#S#...#
#.#.#.#
#...#.#
#####.#
#....E#
#######12
#######
#S#***#
#*#*#*#
#***#*#
#####*#
#....E#
#######📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
* lên từng ô khi lùi từ E về S. Vì mê cung hoàn hảo chỉ có đúng một đường, đáp án duy nhất, thứ tự thử hướng không ảnh hưởng (dùng DFS cũng ra đúng đường này, nhưng nhớ khử đệ quy vì đường có thể dài tới nửa triệu ô). Viền ngoài toàn tường nên không cần kiểm tra ra ngoài lưới.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string g[1005];
int d[1005][1005], pk[1005][1005];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
int sx = 0, sy = 0, ex = 0, ey = 0;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++){
d[i][j] = -1;
if(g[i][j] == 'S'){ sx = i; sy = j; }
if(g[i][j] == 'E'){ ex = i; ey = j; }
}
}
queue<pair<int, int>> q;
d[sx][sy] = 0; q.push({sx, sy});
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(g[nx][ny] == '#' || d[nx][ny] != -1) continue; // viền ngoài luôn là tường
d[nx][ny] = d[x][y] + 1; pk[nx][ny] = k;
q.push({nx, ny});
}
}
int x = ex, y = ey;
while(x != sx || y != sy){ // truy vết, tô '*' mọi ô trên đường
int k = pk[x][y];
x -= dx[k]; y -= dy[k];
if(x != sx || y != sy) g[x][y] = '*';
}
cout << d[ex][ey] << "\n";
for(int i = 0; i < n; i++) cout << g[i] << "\n";
return 0;
}import sys
from collections import deque
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = [list(r) for r in data[2:2 + n]]
for i in range(n):
for j in range(m):
if g[i][j] == 'S': sx, sy = i, j
if g[i][j] == 'E': ex, ey = i, j
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
d = [[-1] * m for _ in range(n)]
pk = [[0] * m for _ in range(n)]
d[sx][sy] = 0
q = deque([(sx, sy)])
while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if g[nx][ny] != '#' and d[nx][ny] == -1: # viền ngoài luôn là tường
d[nx][ny] = d[x][y] + 1
pk[nx][ny] = k
q.append((nx, ny))
x, y = ex, ey
while (x, y) != (sx, sy): # truy vết, tô '*' mọi ô trên đường
k = pk[x][y]
x, y = x - dx[k], y - dy[k]
if (x, y) != (sx, sy):
g[x][y] = '*'
print(d[ex][ey])
print('\n'.join(''.join(r) for r in g))Mê cung $n \times m$ ($1 \le n, m \le 100$) có một S, một E. Em được phá tối đa $k$ bức tường ($0 \le k \le 10$): bước vào ô # nghĩa là phá nó, tốn 1 lần phá và 1 bước như thường. In số bước ít nhất từ S tới E, hoặc $-1$.
4 5 1
S.#..
###.#
..#.E
.....6📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m, K;
string g[105];
int d[11][105][105]; // d[b][x][y]: đã phá b bức tường
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
cin >> n >> m >> K;
int sx = 0, sy = 0, ex = 0, ey = 0;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++){
if(g[i][j] == 'S'){ sx = i; sy = j; }
if(g[i][j] == 'E'){ ex = i; ey = j; }
}
}
memset(d, -1, sizeof d);
queue<array<int, 3>> q;
d[0][sx][sy] = 0;
q.push({0, sx, sy});
while(!q.empty()){
auto [b, x, y] = q.front();
q.pop();
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
int nb = b + (g[nx][ny] == '#'); // bước vào tường: phá thêm 1
if(nb > K || d[nb][nx][ny] != -1) continue;
d[nb][nx][ny] = d[b][x][y] + 1;
q.push({nb, nx, ny});
}
}
int ans = -1;
for(int b = 0; b <= K; b++)
if(d[b][ex][ey] != -1 && (ans == -1 || d[b][ex][ey] < ans)) ans = d[b][ex][ey];
cout << ans;
return 0;
}import sys
from collections import deque
data = sys.stdin.read().split()
n, m, K = int(data[0]), int(data[1]), int(data[2])
g = data[3:3 + n]
for i in range(n):
if 'S' in g[i]: sx, sy = i, g[i].index('S')
if 'E' in g[i]: ex, ey = i, g[i].index('E')
N = n * m
d = [-1] * ((K + 1) * N) # trạng thái (b, x, y) -> chỉ số b*N + x*m + y
wall = [g[i][j] == '#' for i in range(n) for j in range(m)]
d[sx * m + sy] = 0
q = deque([(0, sx, sy)])
while q:
b, x, y = q.popleft()
cur = d[b * N + x * m + y]
for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
if 0 <= nx < n and 0 <= ny < m:
nb = b + wall[nx * m + ny] # bước vào tường: phá thêm 1
if nb <= K and d[nb * N + nx * m + ny] == -1:
d[nb * N + nx * m + ny] = cur + 1
q.append((nb, nx, ny))
res = [d[b * N + ex * m + ey] for b in range(K + 1) if d[b * N + ex * m + ey] != -1]
print(min(res) if res else -1)Mê cung $n \times m$ ($1 \le n, m \le 300$) gồm ., #, ô bùn ~, một S và một E. Bước vào ô . hoặc E mất 1 giây, bước vào ô bùn mất 3 giây. In thời gian ít nhất để từ S tới E, hoặc $-1$.
2 4
S~~E
....5📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string g[505];
long long dist[505][505];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
int sx = 0, sy = 0, ex = 0, ey = 0;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++){
if(g[i][j] == 'S'){ sx = i; sy = j; }
if(g[i][j] == 'E'){ ex = i; ey = j; }
dist[i][j] = LLONG_MAX;
}
}
priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<>> pq;
dist[sx][sy] = 0;
pq.push({0, sx, sy});
while(!pq.empty()){
auto [du, x, y] = pq.top();
pq.pop();
if(du != dist[x][y]) continue; // bản ghi cũ, bỏ qua
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == '#') continue;
long long w = (g[nx][ny] == '~') ? 3 : 1; // giá khi BƯỚC VÀO ô mới
if(du + w < dist[nx][ny]){
dist[nx][ny] = du + w;
pq.push({dist[nx][ny], nx, ny});
}
}
}
cout << (dist[ex][ey] == LLONG_MAX ? -1 : dist[ex][ey]);
return 0;
}import sys, heapq
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
for i in range(n):
if 'S' in g[i]: sx, sy = i, g[i].index('S')
if 'E' in g[i]: ex, ey = i, g[i].index('E')
INF = float('inf')
dist = [INF] * (n * m)
dist[sx * m + sy] = 0
pq = [(0, sx, sy)]
while pq:
du, x, y = heapq.heappop(pq)
if du != dist[x * m + y]: # bản ghi cũ, bỏ qua
continue
for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
if 0 <= nx < n and 0 <= ny < m and g[nx][ny] != '#':
nd = du + (3 if g[nx][ny] == '~' else 1) # giá khi BƯỚC VÀO ô mới
if nd < dist[nx * m + ny]:
dist[nx * m + ny] = nd
heapq.heappush(pq, (nd, nx, ny))
r = dist[ex * m + ey]
print(-1 if r == INF else r)Mê cung $n \times m$ ($1 \le n, m \le 50$) gồm ., #, một S, một E, các chìa khoá a…d và các cửa A…D. Bước vào ô chìa khoá thì nhặt được chìa đó (giữ mãi, dùng mãi). Chỉ bước vào được cửa khi đã có chìa cùng chữ. In số bước ít nhất từ S tới E, hoặc $-1$.
3 5
S.A.E
.###.
a....8📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
a (2 bước), quay lên qua cửa A tới E (6 bước) chỉ mất 8 bước. Chú ý cùng một ô có thể được thăm nhiều lần với $mask$ khác nhau, đó chính là chỗ “quay lại” sau khi nhặt chìa.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string g[55];
int d[16][55][55]; // d[mask][x][y]
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
cin >> n >> m;
int sx = 0, sy = 0;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++)
if(g[i][j] == 'S'){ sx = i; sy = j; }
}
memset(d, -1, sizeof d);
queue<array<int, 3>> q;
d[0][sx][sy] = 0;
q.push({0, sx, sy});
while(!q.empty()){
auto [mask, x, y] = q.front();
q.pop();
if(g[x][y] == 'E'){ cout << d[mask][x][y]; return 0; } // lấy ra theo d tăng dần
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
char c = g[nx][ny];
if(c == '#') continue;
if(c >= 'A' && c <= 'D' && !(mask >> (c - 'A') & 1)) continue; // cửa khoá, chưa có chìa
int nm = mask;
if(c >= 'a' && c <= 'd') nm |= 1 << (c - 'a'); // nhặt chìa khoá
if(d[nm][nx][ny] != -1) continue;
d[nm][nx][ny] = d[mask][x][y] + 1;
q.push({nm, nx, ny});
}
}
cout << -1;
return 0;
}import sys
from collections import deque
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
for i in range(n):
if 'S' in g[i]: sx, sy = i, g[i].index('S')
N = n * m
d = [-1] * (16 * N) # trạng thái (mask, x, y) -> mask*N + x*m + y
d[sx * m + sy] = 0
q = deque([(0, sx, sy)])
ans = -1
while q:
mask, x, y = q.popleft()
cur = d[mask * N + x * m + y]
if g[x][y] == 'E': # lấy ra theo d tăng dần
ans = cur
break
for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
if not (0 <= nx < n and 0 <= ny < m):
continue
c = g[nx][ny]
if c == '#':
continue
if 'A' <= c <= 'D' and not (mask >> (ord(c) - 65) & 1): # cửa khoá, chưa có chìa
continue
nm = mask | (1 << (ord(c) - 97)) if 'a' <= c <= 'd' else mask # nhặt chìa khoá
if d[nm * N + nx * m + ny] == -1:
d[nm * N + nx * m + ny] = cur + 1
q.append((nm, nx, ny))
print(ans)Mê cung $n \times m$ ($1 \le n, m \le 1000$) gồm ., #, một S (em) và một số con quái vật M. Mỗi giây em đi sang một ô kề, các quái vật cũng vậy. Quái vật rất thông minh, nên em chỉ an toàn khi bước vào ô mà em tới sớm hơn hẳn mọi quái vật (nếu một quái vật tới được ô đó sớm hơn hoặc cùng lúc, nó sẽ chờ sẵn). Em thoát khi đứng trên một ô ở biên lưới. In số bước ít nhất để thoát, hoặc $-1$. Nếu S ở biên thì đáp án là 0.
5 7
#######
#S...M#
#.###.#
#.....#
##.####4📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
M (phần 4) cho $dm[x][y]$ = thời điểm sớm nhất có quái vật tới ô; ô quái vật không tới được thì $dm = \infty$. Lần 2: BFS từ S, chỉ bước vào ô kề $v$ khi $d + 1 < dm[v]$. Ô biên đầu tiên được thăm cho đáp án. Ở ví dụ, em đi xuống (2,1), (3,1), (3,2) rồi ra ô biên (4,2) sau 4 bước; quái vật phải đi 5 bước mới tới (3,2), chậm hơn em.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
string g[1005];
int dm[1005][1005], dp[1005][1005]; // dm: quái vật gần nhất tới, dp: người chơi tới
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 1e9;
bool border(int x, int y){ return x == 0 || x == n - 1 || y == 0 || y == m - 1; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
queue<pair<int, int>> q;
int sx = 0, sy = 0;
for(int i = 0; i < n; i++){
cin >> g[i];
for(int j = 0; j < m; j++){
dm[i][j] = INF; dp[i][j] = -1;
if(g[i][j] == 'M'){ dm[i][j] = 0; q.push({i, j}); } // BFS đa nguồn
if(g[i][j] == 'S'){ sx = i; sy = j; }
}
}
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == '#') continue;
if(dm[nx][ny] != INF) continue;
dm[nx][ny] = dm[x][y] + 1;
q.push({nx, ny});
}
}
if(border(sx, sy)){ cout << 0; return 0; }
dp[sx][sy] = 0; q.push({sx, sy});
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
for(int k = 0; k < 4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(g[nx][ny] == '#' || dp[nx][ny] != -1) continue;
if(dp[x][y] + 1 >= dm[nx][ny]) continue; // quái vật tới sớm hơn hoặc cùng lúc
dp[nx][ny] = dp[x][y] + 1;
if(border(nx, ny)){ cout << dp[nx][ny]; return 0; }
q.push({nx, ny});
}
}
cout << -1;
return 0;
}import sys
from collections import deque
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
INF = 10 ** 9
dm = [[INF] * m for _ in range(n)] # quái vật gần nhất tới
dp = [[-1] * m for _ in range(n)] # người chơi tới
q = deque()
for i in range(n):
for j in range(m):
if g[i][j] == 'M': # BFS đa nguồn
dm[i][j] = 0
q.append((i, j))
elif g[i][j] == 'S':
sx, sy = i, j
while q:
x, y = q.popleft()
for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
if 0 <= nx < n and 0 <= ny < m and g[nx][ny] != '#' and dm[nx][ny] == INF:
dm[nx][ny] = dm[x][y] + 1
q.append((nx, ny))
def border(x, y):
return x == 0 or x == n - 1 or y == 0 or y == m - 1
ans = -1
if border(sx, sy):
ans = 0
else:
dp[sx][sy] = 0
q.append((sx, sy))
while q and ans == -1:
x, y = q.popleft()
for nx, ny in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
if g[nx][ny] == '#' or dp[nx][ny] != -1:
continue
if dp[x][y] + 1 >= dm[nx][ny]: # quái vật tới sớm hơn hoặc cùng lúc
continue
dp[nx][ny] = dp[x][y] + 1
if border(nx, ny):
ans = dp[nx][ny]
break
q.append((nx, ny))
print(ans)
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét