Dịch chuyển tức thời
Đề bài
Trong một trò chơi di chuyển trên bảng số có quy tắc như sau:
- Bảng số gồm có $N$ dòng và $M$ cột; các dòng được đánh số 1 đến $N$, từ trên xuống dưới; các cột được đánh số từ 1 đến $M$, từ trái sang phải. Ô ở dòng thứ $u$ giao với cột thứ $v$ được gọi là ô $(u, v)$. Ô $(u, v)$ chứa một số nguyên $A_{uv}$ không âm.
- Từ ô $(u, v)$, người chơi có thể di chuyển sang một ô có chung cạnh: $(u - 1, v)$, $(u + 1, v)$, $(u, v - 1)$, $(u, v + 1)$ hoặc di chuyển sang một ô khác có cùng giá trị, và không thể di chuyển vào ô có giá trị bằng 0. Mỗi lần di chuyển tốn một đơn vị thời gian.
Yêu cầu: cho vị trí ô xuất phát và ô đích, tìm thời gian nhỏ nhất đi từ ô xuất phát về ô đích theo luật của trò chơi.
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên dương $N$ và $M$ là số dòng và số cột của bảng.
- Dòng thứ hai gồm bốn số $x, y, z, t$ mô tả xuất phát ở ô $(x, y)$ và đích ở ô $(z, t)$.
- $N$ dòng sau, mỗi dòng gồm $M$ số nguyên không âm mô tả bảng số.
Kết quả ra: gồm một số nguyên dương là số đơn vị thời gian nhỏ nhất để đi từ ô xuất phát đến ô đích thoả mãn yêu cầu.
Lưu ý: mỗi số nguyên cách nhau một dấu cách. Dữ liệu đảm bảo luôn có đường đi từ xuất phát đến đích.
- Có 40% số test: $N, M \le 100$, $A_{uv} \lt 10^9$ và các số nguyên dương trong bảng phân biệt;
- Có 20% số test khác: $N, M \le 1000$, $A_{uv} \lt 10^9$ và các số nguyên dương trong bảng phân biệt;
- Có 20% số test khác: $N, M \le 1000$, $A_{uv} \lt 10^9$ và các số nguyên dương trong bảng lặp lại không quá hai lần;
- Có 20% số test còn lại: $N, M \le 1000$, $A_{uv} \lt 10^9$ và các số trong bảng có thể lặp lại nhiều lần.
5 4
1 1 5 4
1 2 3 4
5 0 0 6
7 0 8 9
0 0 10 0
11 12 13 149Có thể đi như các đỉnh được tô đậm: 1, 2, 3, 4, 6, 9, 8, 10, 13, 14.
| 1 | 2 | 3 | 4 |
| 5 | 0 | 0 | 6 |
| 7 | 0 | 8 | 9 |
| 0 | 0 | 10 | 0 |
| 11 | 12 | 13 | 14 |
5 4
1 1 5 4
1 2 3 4
5 0 0 6
7 0 8 6
0 0 6 0
3 4 7 94Có thể đi như các đỉnh được tô đậm: 1, 5, 7, 7, 9 (từ ô số 7 ở dòng 3 dịch chuyển tức thời sang ô số 7 ở dòng 5).
| 1 | 2 | 3 | 4 |
| 5 | 0 | 0 | 6 |
| 7 | 0 | 8 | 6 |
| 0 | 0 | 6 | 0 |
| 3 | 4 | 7 | 9 |
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesTóm tắt đề bài một cách đơn giản nhất để bạn nào chưa hiểu: cho 1 mê cung có $n$ dòng và $m$ cột. Từ một ô bất kì ta có thể di chuyển sang một ô chung cạnh hoặc một ô khác có giá trị bằng ô đó, và ta không được di chuyển vào ô có giá trị bằng 0. Ta cần tìm đường đi ngắn nhất từ ô có toạ độ $\{x, y\}$ đến ô có toạ độ $\{z, t\}$ và in ra số bước đi của đường đi ngắn nhất đó. Biết $n, m \le 1000$, $0 \le a[i][j] \lt 10^9$, dữ liệu vào luôn đảm bảo có đường đi; đề bài chia thành 4 subtask lận luôn nha.
dx, dy, chốc nữa mình sẽ nói rõ.Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Tham khảoCách trâu nhất: DFS thử mọi đường đi
Đầu tiên ta hãy thử xét với trường hợp các số nguyên dương trong mê cung là phân biệt. Các bạn cần lưu ý chỗ "các số nguyên dương trong mê cung là phân biệt": số 0 không phải là số nguyên dương nha, nên trong mê cung vẫn có thể có nhiều số 0 đó. Khi các số nguyên dương phân biệt thì không có 2 ô nào cùng giá trị, tức là không thể dịch chuyển tức thời, chỉ đi được sang ô chung cạnh thôi.
Cách làm ta dễ nghĩ tới nhất chính là vét cạn: ta đi thử mọi đường đi có thể có từ đỉnh nguồn đến mọi đỉnh, từ đó liên tục cập nhật mảng dis là mảng lưu khoảng cách từ đỉnh nguồn đến mọi đỉnh. Sau khi thử mọi trường hợp thì mảng dis sẽ lưu khoảng cách ngắn nhất từ đỉnh nguồn đến mọi đỉnh, bao gồm cả đích rồi. Và cách làm trâu nhất là dùng DFS nha; cách này các bạn tham khảo thôi vì nếu mà có chút kiến thức về đồ thị là nhận ra bài này sẽ dùng BFS ngay, mình sẽ nói ở đoạn sau nhé.
Các bạn hiểu DFS tức là mình sẽ đi thăm một đỉnh $\{i, j\}$ chẳng hạn: lúc đầu mình sẽ đánh dấu là đã thăm đỉnh $\{i, j\}$ rồi, sau đó duyệt qua các đỉnh mà từ đỉnh $\{i, j\}$ có thể đi sang được, nếu có đỉnh chưa thăm thì ta sẽ thăm đỉnh đó bằng cách gọi đệ quy.
Mẹo duyệt 4 ô chung cạnh: cách làm gọn nhất là tạo 2 mảng dx, dy lưu các giá trị giúp ta thay đổi $i$, $j$. Đi sang ô bên trên sẽ là $\{i - 1, j + 0\}$; sang ô bên trái là $\{i + 0, j - 1\}$; sang bên phải là $\{i + 0, j + 1\}$; xuống bên dưới là $\{i + 1, j + 0\}$. Vậy ta sẽ lưu dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0}. Từ đó nếu muốn duyệt 4 ô chung cạnh thì chỉ việc dùng 1 vòng for rồi cộng lần lượt dx[k], dy[k] vào $i$, $j$ là được rồi.
int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
for(int k = 0; k < 4; ++k){
int adjx = i + dx[k], adjy = j + dy[k];
// {adjx, adjy} là ô chung cạnh thứ k của ô {i, j}
}Mẹo không cần kiểm tra ra ngoài bảng: ta còn phải check các ô chung cạnh đó có nằm trong mảng không; ví dụ ta đang ở vị trí $\{1, 1\}$ thì sẽ không có ô bên trên hay ô bên trái. Giải pháp của mình ở đây là: vì ta không thể đi tới các ô có giá trị bằng 0, mà lúc khai báo biến toàn cục thì mặc định mọi phần tử sẽ bằng 0, vậy ta sẽ khai báo mảng a là mảng toàn cục và khai báo thừa ra để có các phần tử ngoài rìa, ví dụ int a[1005][1005]. Ta sẽ chỉ dùng từ $\{1, 1\}$ đến tối đa $\{1000, 1000\}$ thôi, còn các giá trị nằm ngoài sẽ mặc định là 0. Vậy khi duyệt ta chỉ cần check xem ô ta định tới có khác 0 không là được.
Sau đây là source code cho các bạn tham khảo cách làm trên nha, lưu ý là chỉ đúng khi các số nguyên dương phân biệt thôi đó:
Xem code DFS (chỉ để tham khảo)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1000;
int n, m;
int a[N + 5][N + 5];
bool visited[N + 5][N + 5];
int dis[N + 5][N + 5], dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
void findShortestPathDFS(int i, int j){
visited[i][j] = true;
for(int k = 0; k < 4; ++k){
int adjx = i + dx[k], adjy = j + dy[k];
if(a[adjx][adjy] && !visited[adjx][adjy]){
dis[adjx][adjy] = min(dis[adjx][adjy], dis[i][j] + 1);
findShortestPathDFS(adjx, adjy);
}
}
visited[i][j] = false;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int x, y, z, t;
cin >> n >> m >> x >> y >> z >> t;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> a[i][j];
}
}
fill(&dis[0][0], &dis[N + 4][N + 5], INT_MAX);
dis[x][y] = 0;
findShortestPathDFS(x, y);
cout << dis[z][t];
return 0;
}Giải thích một số chỗ trong cách làm trên:
- Hàm
findShortestPathDFS(int i, int j): đầu tiên ta đánh dấu đỉnh $\{i, j\}$ là đã thăm, tức làtrue(mặc định khi khai báo biến toàn cục thì tất cả đều làfalse, ta quy ước là chưa thăm). Sau đó ta đi duyệt các đỉnh chung cạnh với nó.if(a[adjx][adjy] && !visited[adjx][adjy])nghĩa là đầu tiên ta checka[adjx][adjy]có khác 0 không, nếu có thì check tiếp đỉnh $\{adjx, adjy\}$ đã được thăm chưa. Nếu chưa thì ta cập nhậtdislà khoảng cách thấp nhất có thể, sau đó gọi đệ quy. Vì ta đang thử mọi đường đi có thể nên sau cùng ta lại phải gánvisited[i][j] = false;để thử sang đường đi khác nha. ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài mà cần nhập xuất nhiều thì ta nên sử dụng 2 dòng này; ví dụ với bài này thì đầu vào có thể lên tới $10^6$ số. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.fill(&dis[0][0], &dis[N + 4][N + 5], INT_MAX);là ta điền toàn bộ mảngdisbằng số to nhất, để có thể cập nhậtmin, vì mọi giá trị lần đầu tiên so sánh sẽ đều nhỏ hơnINT_MAXmà cập nhật lại. Nếu không làm vậy thì mặc định mọi phần tử trong mảngdissẽ bằng 0 vì ta khai báo là biến toàn cục.dis[x][y] = 0;tất nhiên là khoảng cách từ đỉnh nguồn tới chính nó bằng 0 rồi. Sau khi chạy xong hàm trên ta chỉ việc in radis[z][t]là khoảng cách ngắn nhất tới đỉnh $\{z, t\}$.
Với cách trên thì chắc chắn ta không thể AC (Accepted – được chấp nhận) được bài này rồi; thậm chí chúng ta còn chưa chắc có thể ăn được hoàn toàn subtask 1 cơ, vì số đường đi trên lưới tăng theo cấp số mũ, và đệ quy sâu tới hàng chục nghìn tầng còn có thể tràn stack nữa.
60%Subtask 1, 2: các số nguyên dương phân biệt – BFS
Mình gộp subtask 1 với 2 vào làm 1 vì với cách dùng BFS thì ta hoàn toàn có thể ăn được cả subtask 1 và 2 rồi. Thậm chí cách làm bằng BFS này còn đơn giản và dễ cài đặt hơn cách trên đó.
Thuật toán BFS sẽ ưu tiên mở rộng các đỉnh gần đỉnh nguồn hơn, từ đó với đồ thị không có trọng số thì BFS sẽ cho đường đi ngắn nhất giữa 2 đỉnh. Ở bài trên, để đi từ vị trí này sang vị trí khác chung cạnh thì ta đều tốn 1 đơn vị thời gian, hay chính là đồ thị không có trọng số đó.
Mở đầu việc cài đặt BFS thì ta vẫn cần mảng dis để lưu khoảng cách, mảng dx, dy giúp ta di chuyển. Ta cần 1 queue (hàng đợi) rỗng; đầu tiên cho đỉnh nguồn vào đó, đánh dấu là đã thăm và khoảng cách đến nó dĩ nhiên bằng 0. Rồi ta lặp chừng nào hàng đợi còn phần tử: lấy đỉnh đầu ra, gọi là đỉnh $\{i, j\}$, xoá nó khỏi hàng đợi; duyệt các đỉnh mà từ đỉnh $\{i, j\}$ có thể đi tới (ở đây là các đỉnh chung cạnh và khác 0); nếu chưa thăm thì cập nhật khoảng cách cho chúng – cái hay ở đây là ta chỉ việc gán luôn khoảng cách bằng dis[i][j] + 1 vì BFS luôn cho ta đường đi ngắn nhất – rồi đưa đỉnh đó vào hàng đợi và đánh dấu đã thăm. Bạn nào còn chưa rõ thì mình tiến cử tham khảo về BFS ở link này nha: VNOI Wiki – Tìm kiếm theo chiều rộng.
Và để tối ưu thì: trong quá trình BFS thường ta sẽ có đường đi ngắn nhất từ đỉnh nguồn đến mọi đỉnh, nhưng ở bài này ta chỉ cần từ đỉnh nguồn tới đỉnh đích thôi. Cho nên khi BFS chạm tới đỉnh đích thì đó cũng đồng thời là khoảng cách ngắn nhất cần tìm, ta dừng BFS và trả về khoảng cách đó luôn nha.
Xem code subtask 1, 2 (BFS)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1000;
int n, m;
int a[N + 5][N + 5];
bool visited[N + 5][N + 5];
int dis[N + 5][N + 5], dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
int findShortestPathBFS(int x, int y, int z, int t){
queue<ii> q;
q.push((ii){x, y});
visited[x][y] = true;
dis[x][y] = 0;
if(z == x && t == y){
return 0;
}
while(!q.empty()){
int i = q.front().first, j = q.front().second;
q.pop();
for(int k = 0; k < 4; ++k){
int adjx = i + dx[k], adjy = j + dy[k];
if(a[adjx][adjy] && !visited[adjx][adjy]){
dis[adjx][adjy] = dis[i][j] + 1;
if(adjx == z && adjy == t){
return dis[z][t];
}
q.push((ii){adjx, adjy});
visited[adjx][adjy] = true;
}
}
}
return dis[z][t];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int x, y, z, t;
cin >> n >> m >> x >> y >> z >> t;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> a[i][j];
}
}
cout << findShortestPathBFS(x, y, z, t);
return 0;
}import sys
from collections import deque
N = 1000
a = [[0] * (N + 5) for _ in range(N + 5)]
visited = [[False] * (N + 5) for _ in range(N + 5)]
dis = [[10**18] * (N + 5) for _ in range(N + 5)]
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
def findShortestPathBFS(x, y, z, t, n, m):
q = deque()
q.append((x, y))
visited[x][y] = True
dis[x][y] = 0
if z == x and t == y:
return 0
while q:
i, j = q.popleft()
for k in range(4):
adjx, adjy = i + dx[k], j + dy[k]
if 1 <= adjx <= n and 1 <= adjy <= m:
if a[adjx][adjy] and not visited[adjx][adjy]:
dis[adjx][adjy] = dis[i][j] + 1
if adjx == z and adjy == t:
return dis[z][t]
q.append((adjx, adjy))
visited[adjx][adjy] = True
return dis[z][t]
data = list(map(int, sys.stdin.read().strip().split()))
n, m, x, y, z, t = data[:6]
arr = data[6:]
idx = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
a[i][j] = arr[idx]
idx += 1
print(findShortestPathBFS(x, y, z, t, n, m))Giải thích một số chỗ trong cách làm trên:
queue<ii> q; q.push((ii){x, y});– mình đãtypedef pair<int, int> ii;nên tạo 1 hàng đợi với các phần tử là pair; lúc push vào thì mình ép kiểu(ii)thôi.if(z == x && t == y)– nếu đích trùng với xuất phát thì trả về 0 luôn; nếu không làm vậy thì trường hợp này thuật toán sẽ duyệt qua toàn mảng luôn đó.int i = q.front().first, j = q.front().second;là lấy phần tử đầu của queue;q.pop()là xoá đỉnh đầu vừa lấy khỏi hàng đợi.if(adjx == z && adjy == t)– gặp đích là dừng BFS rồi trả về kết quả luôn nha.
Đánh giá độ phức tạp:
- Không gian: $O(3 \cdot N^2)$ vì ta dùng tận 3 mảng kích cỡ $[N][N]$.
- Thời gian: $O(6 \cdot n \cdot m)$. Lúc đọc vào mất $O(n \cdot m)$; độ phức tạp của BFS là $O(V + E)$ (số đỉnh + số cạnh), bài trên có $n \cdot m$ đỉnh và mỗi đỉnh nối với 4 đỉnh nên có khoảng $4 \cdot n \cdot m$ cạnh, BFS là $O(5 \cdot n \cdot m)$. Tổng lại là $O(6 \cdot n \cdot m)$.
Với cách trên thì ta mới ăn được 59/100 test thôi, chỉ ăn được các trường hợp mà các số nguyên dương trong mê cung là phân biệt.
+20%Subtask 3: số lặp lại không quá 2 lần – thêm cạnh "dịch chuyển" bằng map
Ở subtask này thì các số nguyên dương có thể bị lặp lại nha. Vậy từ đỉnh $\{i, j\}$ ta không chỉ có thể đi qua 4 đỉnh chung cạnh nữa mà còn có thể đi qua các đỉnh có cùng giá trị. Giải pháp của ta sẽ là dùng map để lưu vị trí các đỉnh có cùng giá trị, phần tử của map sẽ là một vector<ii>; lưu ý là ta sẽ không lưu các giá trị 0 nha.
dis = 3. Từ ô đó ta có thể dịch chuyển sang bất kì ô có giá trị 5 khác, nên dis của 3 ô số 5 còn lại (ô 5 số 2, 3, 4) sẽ bằng 4. Sau đó khi ta duyệt tới ô 5 số 2, thì các ô 5 số 1, 3, 4 cũng là các đỉnh kề với nó, vậy có cần duyệt lại không? Câu trả lời là không: bước sang ô 5 số 3 hoặc 4 thì dis của chúng sẽ lên 5, chỉ có tăng; còn bước về ô 5 số 1 thì cũng chẳng để làm gì. Kết luận: khi các đỉnh có cùng giá trị đã được duyệt 1 lần rồi thì không cần duyệt lại lần nữa, duyệt lại cũng không thay đổi được kết quả.Điều trên vô cùng quan trọng nha, vì nếu không có điều trên thì ô 5 số 1 duyệt qua ô 5 số 2, 3, 4 mất 3 bước; rồi ô 5 số 2 lại đi sang ô 5 số 1, 3, 4 mất 3 bước nữa; cứ vậy tổng cộng mất tận 12 bước. Với $k$ ô cùng giá trị thì sẽ thành $k^2$ bước, mà $k$ có thể lên tới $10^6$ thì TLE chắc luôn. Vậy ta cần thêm 1 map nữa để check rằng với 1 giá trị bất kì, ta đã duyệt qua các đỉnh có cùng giá trị đó chưa. Nếu chưa thì duyệt, nếu rồi thì thôi.
Em nhập bảng (các dòng cách nhau bởi dấu /), ô xuất phát, ô đích rồi bấm Tiếp để xem BFS loang từng ô: số nhỏ ở góc mỗi ô là dis, ô viền tím là ô được dịch chuyển tức thời tới (mỗi giá trị chỉ dịch chuyển 1 lần):
Xem code subtask 3 (BFS + map)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1000;
int n, m;
int a[N + 5][N + 5];
bool visited[N + 5][N + 5];
int dis[N + 5][N + 5], dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
map<int, vector<ii>> mp;
map<int, bool> visitedVal;
int findShortestPathBFS(int x, int y, int z, int t){
visitedVal[0] = true;
queue<ii> q;
q.push((ii){x, y});
visited[x][y] = true;
dis[x][y] = 0;
if(z == x && t == y){
return 0;
}
while(!q.empty()){
int i = q.front().first, j = q.front().second;
q.pop();
for(int k = 0; k < 4; ++k){
int adjx = i + dx[k], adjy = j + dy[k];
if(a[adjx][adjy] && !visited[adjx][adjy]){
dis[adjx][adjy] = dis[i][j] + 1;
if(adjx == z && adjy == t){
return dis[z][t];
}
q.push((ii){adjx, adjy});
visited[adjx][adjy] = true;
}
}
if(!visitedVal[a[i][j]]){
for(ii tmp : mp[a[i][j]]){
if(!visited[tmp.first][tmp.second]){
dis[tmp.first][tmp.second] = dis[i][j] + 1;
if(tmp.first == z && tmp.second == t){
return dis[z][t];
}
q.push((ii){tmp.first, tmp.second});
visited[tmp.first][tmp.second] = true;
}
}
visitedVal[a[i][j]] = true;
}
}
return dis[z][t];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int x, y, z, t;
cin >> n >> m >> x >> y >> z >> t;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> a[i][j];
if(a[i][j]){
mp[a[i][j]].push_back((ii){i, j});
}
}
}
cout << findShortestPathBFS(x, y, z, t);
return 0;
}import sys
from collections import deque, defaultdict
N = 1000
a = [[0] * (N + 5) for _ in range(N + 5)]
visited = [[False] * (N + 5) for _ in range(N + 5)]
dis = [[10**18] * (N + 5) for _ in range(N + 5)]
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
mp = defaultdict(list)
visitedVal = defaultdict(bool)
def findShortestPathBFS(x, y, z, t, n, m):
visitedVal[0] = True
q = deque()
q.append((x, y))
visited[x][y] = True
dis[x][y] = 0
if z == x and t == y:
return 0
while q:
i, j = q.popleft()
for k in range(4):
adjx, adjy = i + dx[k], j + dy[k]
if 1 <= adjx <= n and 1 <= adjy <= m:
if a[adjx][adjy] and not visited[adjx][adjy]:
dis[adjx][adjy] = dis[i][j] + 1
if adjx == z and adjy == t:
return dis[z][t]
q.append((adjx, adjy))
visited[adjx][adjy] = True
if not visitedVal[a[i][j]]:
for (u, v) in mp[a[i][j]]:
if not visited[u][v]:
dis[u][v] = dis[i][j] + 1
if u == z and v == t:
return dis[z][t]
q.append((u, v))
visited[u][v] = True
visitedVal[a[i][j]] = True
return dis[z][t]
data = list(map(int, sys.stdin.read().strip().split()))
n, m, x, y, z, t = data[:6]
arr = data[6:]
idx = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
a[i][j] = arr[idx]
if a[i][j]:
mp[a[i][j]].append((i, j))
idx += 1
print(findShortestPathBFS(x, y, z, t, n, m))Giải thích một số chỗ trong cách làm trên:
map<int, vector<ii>> mp; map<int, bool> visitedVal;– 2 map lần lượt dùng để lưu vị trí của các giá trị trùng nhau và check xem với 1 giá trị bất kì ta đã từng duyệt qua các đỉnh có cùng giá trị đó chưa.visitedVal[0] = true;– ta gán vậy vì giá trị 0 không được xét nên không có chuyện dịch chuyển giữa các ô 0.if(!visitedVal[a[i][j]])– check xem với giá trịa[i][j]thì các đỉnh trùng với nó ta đã duyệt chưa.for(ii tmp : mp[a[i][j]])– duyệt qua danh sách các vị trí có giá trị bằnga[i][j]bằng vòng lặp for each; biếntmpsẽ lần lượt bằng từng phần tử trong vector đó.if(!visited[tmp.first][tmp.second])– check đỉnh đó đã thăm chưa, rồi làm tương tự ở trên: gándis = dis[i][j] + 1, gặp đích thì dừng BFS và trả về luôn, không thì cho vào hàng đợi và đánh dấu đã thăm.visitedVal[a[i][j]] = true;– đánh dấu rằng với giá trịa[i][j]thì các đỉnh có giá trị đó đã được duyệt rồi.if(a[i][j]) mp[a[i][j]].push_back((ii){i, j});– lúc đọc vào, ô nào khác 0 thì push vị trí của nó vào vector tương ứng.
Đánh giá độ phức tạp:
- Không gian: tốn hơn subtask 1, 2 vì dùng thêm 2 map, nhưng với giới hạn đề bài cho là 1 GB thì không phải lo nha.
- Thời gian: cách trên thậm chí chạy đúng với các giá trị lặp nhiều hơn 2 lần. Nhưng nó sẽ bị chậm ở chỗ thêm phần tử vào map mất $O(\log N)$, thêm $n$ phần tử là $O(n \log n)$, và map bản chất là cây cân bằng nên còn mất thêm thời gian cân bằng lại cây mỗi lần thêm vào. Chưa kể mỗi lần truy cập 1 phần tử trong map lại tốn $\log N$, nên ta sẽ bị TLE ở những test có rất nhiều giá trị.
Cách trên thì ta sẽ không còn bị WA (wrong answer – trả đáp án sai) nữa mà chỉ bị TLE (time limit exceeded – quá thời gian) ở một số test. Với code C++ thì được 80/100, còn code Python thì được 88/100.
map thành unordered_map, tức là lưu theo hash table (bảng băm) thay vì tree (cây), thì chi phí tìm kiếm trung bình chỉ là $O(1)$ cho mỗi lần tìm và không tốn chi phí cân bằng cây. Thực tế sửa lại một chút như vậy thôi mà code C++ nộp được 99/100, thêm 11 test; code Python được 89/100, thêm 1 test.
// Sửa 2 dòng khai báo:
map<int, vector<ii>> mp;
map<int, bool> visitedVal;
// thành:
unordered_map<int, vector<ii>> mp;
unordered_map<int, bool> visitedVal;unordered_map trường hợp xấu nhất khi tìm 1 phần tử có thể lên đến $O(N)$ nhé các bạn, đó là khi hàm băm không tốt dẫn đến xung đột. Trong khi map lưu theo cơ chế cây nên mọi trường hợp đều đảm bảo $O(\log N)$, nên tuy độ phức tạp cao hơn nhưng dùng map sẽ yên tâm hơn. Vậy không phải lúc nào dùng unordered_map cũng tốt hơn map 🤣. Kinh nghiệm là nếu code dùng map mà bị TLE thì cứ thử thay bằng unordered_map rồi nộp lại xem, nếu được thêm test thì tốt, còn nếu thấy 1 số test đang từ AC chuyển sang TLE thì quay xe lại map thôi 🤪100%Subtask 4: rời rạc hoá (nén số) + danh sách kề – AC
Ta nhận ra rằng để AC được bài này thì phải tìm cách không dùng map mà vẫn truy xuất được vị trí của các đỉnh có cùng giá trị, và vẫn check được với 1 giá trị bất kì ta đã duyệt qua các vị trí cùng giá trị với nó chưa. Ở trên ta dùng map vì $a[i][j] \lt 10^9$, ta không thể tạo mảng $10^9$ phần tử được vì sẽ tràn bộ nhớ. Vậy để AC được ta cần biết tới phương pháp rời rạc hoá, hay trong lập trình thi đấu quen gọi là kĩ thuật nén số. Bạn nào chưa biết thì mình tiến cử link này nha: VNOI Wiki – Rời rạc hoá và ứng dụng.
Đúng như tên gọi thôi, ta sẽ nén số lại sao cho nó nhỏ hơn để vừa với tầm mà ta có thể kiểm soát, và vẫn giữ được quan hệ lớn bé. Ví dụ mảng a = {100, 10, 1000, 25, 100} sẽ được nén thành a = {3, 1, 4, 2, 3}:
| Vị trí | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| a ban đầu | 100 | 10 | 1000 | 25 | 100 |
| a sau khi nén | 3 | 1 | 4 | 2 | 3 |
Ta vẫn giữ được các mối quan hệ lớn bé hay bằng mà số đã nhỏ hơn rất nhiều rồi đó. Và dù mảng có 5 số rất to như $\{10^9, 10^9 + 1, 10^9 + 2, 10^9 + 3, 10^9 + 4\}$ thì cũng nén về $\{1, 2, 3, 4, 5\}$; vậy các số nén về sẽ nằm trong khoảng từ 1 tới kích thước của mảng. Mê cung có tối đa $10^6$ phần tử, vậy ta hoàn toàn có thể nén các số trong mê cung (ngoại trừ số 0) về các giá trị từ 1 tới $10^6$. Sau khi nén, ta dùng danh sách kề (1 mảng các vector) để lưu vị trí các đỉnh có cùng giá trị, và 1 mảng đánh dấu visitedVal để check giá trị đó đã được duyệt chưa.
Về cài đặt: ta cần 1 biến lưu được giá trị của đỉnh và vị trí của đỉnh đó. Các bạn có thể dùng tuple nhưng để code gọn và dễ hiểu nhất thì mình dùng struct: tạo kiểu dữ liệu mới là Data gồm 3 biến int val, i, j. Ta tạo hàm init() giúp đọc đầu vào, nén số và lưu vị trí các đỉnh có cùng giá trị:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1000;
struct Data {
int val, i, j;
};
int n, m, x, y, z, t;
int a[N + 5][N + 5];
vector<ii> adj[N * N + 5];
void init(){
cin >> n >> m >> x >> y >> z >> t;
vector<Data> b;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> a[i][j];
if(a[i][j]){
b.push_back((Data){a[i][j], i, j});
}
}
}
sort(b.begin(), b.end(),
[](const Data &a, const Data &b) -> bool {
return a.val < b.val;
});
a[b[0].i][b[0].j] = 1;
adj[1].push_back((ii){b[0].i, b[0].j});
int cnt = 1;
for(int i = 1; i < (int)b.size(); ++i){
if(b[i].val != b[i - 1].val){
cnt++;
}
a[b[i].i][b[i].j] = cnt;
adj[cnt].push_back((ii){b[i].i, b[i].j});
}
}Giải thích hàm init() ở trên:
vector<ii> adj[N * N + 5];– danh sách kề lưu vị trí các đỉnh có cùng giá trị; mảng có tối đa $10^6 = 10^3 \cdot 10^3$ phần tử nên giá trị sau nén tối đa là $10^6$, chỉ cần độ lớn $N \cdot N + 5$ (thừa ra 5 cho chắc).vector<Data> b;– vector lưu lại giá trị + vị trí của các đỉnh.if(a[i][j]) b.push_back((Data){a[i][j], i, j});– chỉ đỉnh nào khác 0 mới cho vào, và nhớ ép kiểu dữ liệu nha.sort(...)– mình dùng biểu thức lambda để sort vectorbtăng dần theoval. Vì chỉ sort một lần nên viết lambda cho gọn; bạn nào không quen thì hoàn toàn có thể viết hàmcompriêng.a[b[0].i][b[0].j] = 1;– phần tử nhỏ nhất trong mê cung được nén thành 1, vàadj[1].push_back(...)cho vị trí của nó vào danh sách kề của giá trị 1.int cnt = 1và vòng for bên dưới: duyệtbtừ phần tử thứ 2, nếu giá trị khác phần tử trước đó thì tăngcnt; gána[b[i].i][b[i].j] = cntrồi cho vị trí đó vàoadj[cnt].
Vậy chỉ cần gọi init() là ta đã đọc xong đầu vào, nén số và làm xong danh sách kề rồi. Giờ ta thực hiện như subtask 3 thôi, khác ở chỗ không dùng map nữa mà dùng danh sách kề và 1 mảng đánh dấu visitedVal có độ lớn $N \cdot N + 5$.
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 1000;
struct Data {
int val, i, j;
};
int n, m, x, y, z, t;
int a[N + 5][N + 5];
vector<ii> adj[N * N + 5];
void init(){
cin >> n >> m >> x >> y >> z >> t;
vector<Data> b;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> a[i][j];
if(a[i][j]){
b.push_back((Data){a[i][j], i, j});
}
}
}
sort(b.begin(), b.end(),
[](const Data &a, const Data &b) -> bool {
return a.val < b.val;
});
a[b[0].i][b[0].j] = 1;
adj[1].push_back((ii){b[0].i, b[0].j});
int cnt = 1;
for(int i = 1; i < (int)b.size(); ++i){
if(b[i].val != b[i - 1].val){
cnt++;
}
a[b[i].i][b[i].j] = cnt;
adj[cnt].push_back((ii){b[i].i, b[i].j});
}
}
bool visited[N + 5][N + 5], visitedVal[N * N + 5];
int dis[N + 5][N + 5], dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
int findShortestPathBFS(){
visitedVal[0] = true;
queue<ii> q;
q.push((ii){x, y});
visited[x][y] = true;
dis[x][y] = 0;
while(!q.empty()){
int i = q.front().first, j = q.front().second;
q.pop();
for(int k = 0; k < 4; ++k){
int adjx = i + dx[k], adjy = j + dy[k];
if(a[adjx][adjy] && !visited[adjx][adjy]){
dis[adjx][adjy] = dis[i][j] + 1;
if(adjx == z && adjy == t){
return dis[z][t];
}
q.push((ii){adjx, adjy});
visited[adjx][adjy] = true;
}
}
if(!visitedVal[a[i][j]]){
for(ii tmp : adj[a[i][j]]){
if(!visited[tmp.first][tmp.second]){
dis[tmp.first][tmp.second] = dis[i][j] + 1;
if(tmp.first == z && tmp.second == t){
return dis[z][t];
}
q.push((ii){tmp.first, tmp.second});
visited[tmp.first][tmp.second] = true;
}
}
visitedVal[a[i][j]] = true;
}
}
return dis[z][t];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
init();
cout << findShortestPathBFS();
return 0;
}import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
n, m, x, y, z, t = map(int, data[:6])
W = m + 2
a = [0] * ((n + 2) * W) # mảng 1 chiều có viền 0 xung quanh
idx = 6
for i in range(1, n + 1):
base = i * W
for j in range(1, m + 1):
a[base + j] = int(data[idx]); idx += 1
# nén số: mỗi giá trị khác 0 -> 1 số thứ tự, đồng thời gom các ô cùng giá trị
comp = {}
adj = []
for p in range(len(a)):
v = a[p]
if v:
c = comp.get(v)
if c is None:
c = comp[v] = len(adj)
adj.append([])
adj[c].append(p)
a[p] = c + 1 # giá trị sau nén nằm trong [1, số giá trị khác nhau]
visitedVal = [False] * (len(adj) + 1)
visitedVal[0] = True
src, dst = x * W + y, z * W + t
if src == dst:
print(0); return
dis = [-1] * len(a)
dis[src] = 0
q = deque([src])
while q:
u = q.popleft()
d = dis[u] + 1
for v in (u - W, u - 1, u + 1, u + W):
if a[v] and dis[v] < 0:
dis[v] = d
if v == dst:
print(d); return
q.append(v)
c = a[u]
if not visitedVal[c]:
visitedVal[c] = True
for v in adj[c - 1]:
if dis[v] < 0:
dis[v] = d
if v == dst:
print(d); return
q.append(v)
print(dis[dst])
main()Đánh giá độ phức tạp:
- Không gian: $O(6 \cdot N^2)$ vì dùng thêm 1 danh sách kề, 1 mảng
visitedVal, 1 vectorb. Nhưng với giới hạn 1 GB thì các bạn không phải lo nha. - Thời gian: $O(nm \log(nm) + 8nm)$: thêm 1 lần sắp xếp vector
btốn $nm \log(nm)$; duyệt vectorbtốn tối đa $nm$; và tổng số lần duyệt danh sách kề trongif(!visitedVal[a[i][j]]) { for(ii tmp : adj[a[i][j]]) ... }cũng chỉ tối đa $nm$ (vì mỗi giá trị chỉ duyệt 1 lần). Lưu ý log ở đây là $\log_2$; tính sơ qua ta được khoảng $3 \cdot 10^7$ phép tính, dự đoán khoảng 0.3 giây cho trường hợp xấu nhất. Thực tế khi nộp thì test lâu nhất dao động 0.5 – 0.6 giây, vì nhiều lúc server đang chạy nhiều hoạt động.
Vậy với cách trên thì ta đã AC được bài này rồi.
Bản gốc của subtask 4 chỉ có C++, mình viết thêm bản Python cùng ý tưởng (nén số bằng dict, lưu lưới vào mảng 1 chiều có viền 0 để chạy nhanh hơn). Mình đã kiểm tra tất cả các bản code với 600 bảng ngẫu nhiên so với cách BFS trâu, đều cho cùng kết quả. Với bảng $1000 \times 1000$ toàn số phân biệt, bản C++ subtask 4 chạy khoảng 0.4 giây, còn bản Python khoảng 2.4 giây (bảng có nhiều số trùng thì nhanh hơn nhiều vì dịch chuyển tức thời tới đích sớm).