Hướng dẫn giải của Leo núi_ HiKing20
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán Leo núi (HiKing20) yêu cầu tìm đường đi từ ô (1, 1) đến ô (N, N) trên một lưới N x N với các ô có độ cao ngẫu nhiên. Điều kiện của đường đi là chênh lệch độ cao giữa ô cao nhất và ô thấp nhất trên đường đi phải nhỏ nhất có thể (chênh lệch tối thiểu). Nói cách khác, ta cần tìm một đường đi sao choR - L là nhỏ nhất, trong đó R là độ cao lớn nhất và L là độ cao nhỏ nhất trên đường đi đó.
Các cách tiếp cận
Cách Thử tất cả các khoảng độ cao (Brute Force)
#include <bits/stdc++.h>
using namespace std;
int N;
int h[205][205];
bool visited[205][205];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool bfs(int L, int R) {
if (h[1][1] < L || h[1][1] > R || h[N][N] < L || h[N][N] > R) return false;
memset(visited, 0, sizeof(visited));
queue<pair<int,int>> q;
q.push({1,1});
visited[1][1] = true;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == N && y == N) return true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && nx <= N && ny >= 1 && ny <= N && !visited[nx][ny]) {
if (h[nx][ny] >= L && h[nx][ny] <= R) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
return false;
}
int main() {
freopen("HIKING20.INP", "r", stdin);
freopen("HIKING20.OUT", "w", stdout);
cin >> N;
int mn = 200, mx = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> h[i][j];
mn = min(mn, h[i][j]);
mx = max(mx, h[i][j]);
}
}
int ans = mx - mn;
for (int L = mn; L <= mx; L++) {
for (int R = L; R <= mx; R++) {
if (bfs(L, R)) {
ans = R - L;
break;
}
}
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(mx^2 * N^2) ~ O(200^2 * N^2)
- Space Complexity: O(N^2)
Phương pháp này thử tất cả các cặp (L, R) sao cho L <= R. Với mỗi cặp, nó sử dụng BFS để kiểm tra xem có đường đi nào từ (1,1) đến (N,N) chỉ đi qua các ô có độ cao trong khoảng [L, R] hay không. Ta lưu lại chênh lệch nhỏ nhất tìm được.
- Cải tiến: Thay vì duyệt tất cả các cặp, ta có thể duyệt L và tìm R nhỏ nhất sao cho đường đi tồn tại (dùng kỹ thuật hai con trỏ hoặc binary search). Tuy nhiên, phương pháp này vẫn chậm.
Cách Tối ưu bằng Binary Search trên chênh lệch
#include <bits/stdc++.h>
using namespace std;
int N;
int h[205][205];
bool visited[205][205];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
// Kiểm tra với chênh lệch tối đa là diff
bool can(int diff) {
int min_h = 200, max_h = 0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++) {
min_h = min(min_h, h[i][j]);
max_h = max(max_h, h[i][j]);
}
// Thử tất cả các mức L có thể
for (int L = min_h; L <= max_h; L++) {
int R = L + diff;
if (h[1][1] < L || h[1][1] > R) continue;
if (h[N][N] < L || h[N][N] > R) continue;
memset(visited, 0, sizeof(visited));
queue<pair<int,int>> q;
q.push({1,1});
visited[1][1] = true;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == N && y == N) return true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && nx <= N && ny >= 1 && ny <= N && !visited[nx][ny]) {
if (h[nx][ny] >= L && h[nx][ny] <= R) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
}
return false;
}
int main() {
freopen("HIKING20.INP", "r", stdin);
freopen("HIKING20.OUT", "w", stdout);
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> h[i][j];
}
}
int low = 0, high = 200, ans = 200;
while (low <= high) {
int mid = (low + high) / 2;
if (can(mid)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(log(200) * 200 * N^2) ~ O(200 * N^2)
- Space Complexity: O(N^2)
Thay vì tìm đáp án trực tiếp, ta dùng Binary Search để tìm giá trị chênh lệch nhỏ nhất (mid) sao cho tồn tại đường đi.
- Với mỗi giá trị mid, ta cần kiểm tra xem có đường đi thỏa mãn chênh lệch <= mid hay không.
- Để kiểm tra mid, ta thử tất cả các mức độ cao thấp nhất L (trong khoảng minheight đến maxheight của bản đồ). Với mỗi L, ta lấy R = L + mid và chạy BFS/DFS xem có đường đi trong khoảng [L, R] không.
- Binary Search giúp giảm số lần kiểm tra từ O(K^2) xuống O(log K).
Cách Tối ưu bằng Binary Search và chỉ thử L là độ cao ô đầu hoặc các ô kề
#include <bits/stdc++.h>
using namespace std;
int N;
int h[205][205];
bool visited[205][205];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool bfs(int L, int R) {
if (h[1][1] < L || h[1][1] > R) return false;
if (h[N][N] < L || h[N][N] > R) return false;
memset(visited, 0, sizeof(visited));
queue<pair<int,int>> q;
q.push({1,1});
visited[1][1] = true;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == N && y == N) return true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && nx <= N && ny >= 1 && ny <= N && !visited[nx][ny]) {
if (h[nx][ny] >= L && h[nx][ny] <= R) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
return false;
}
int main() {
// freopen("HIKING20.INP", "r", stdin);
// freopen("HIKING20.OUT", "w", stdout);
if (!(cin >> N)) return 0;
vector<int> heights;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> h[i][j];
heights.push_back(h[i][j]);
}
}
sort(heights.begin(), heights.end());
heights.erase(unique(heights.begin(), heights.end()), heights.end());
int ans = 200;
// Tối ưu: L chỉ cần thử các độ cao xuất hiện trong lưới (hoặc ít nhất là độ cao của ô đầu)
// Tuy nhiên, để chắc chắn, ta có thể thử mọi L trong heights.
// Hoặc tốt hơn: Binary search chênh lệch, và với mỗi chênh lệch, thử các L.
int low = 0, high = 200;
while (low <= high) {
int mid = (low + high) / 2;
bool found = false;
// Thử mọi độ cao L có thể (lấy từ các ô trong bản đồ)
for (int L : heights) {
if (L > h[1][1]) break; // Optimization: L không nên lớn hơn độ cao ô đầu nếu ta muốn bắt đầu ở đó
// Thực ra L có thể lớn hơn h[1][1] nếu h[1][1] nằm trong [L, L+mid]
// Do đó chỉ cần kiểm tra điều kiện range
int R = L + mid;
if (bfs(L, R)) {
found = true;
break;
}
}
if (found) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(N^2 * log(200) * (N^2 + N^2)) ~ O(N^4 log H)
- Space Complexity: O(N^2)
Đây là phiên bản tối ưu nhất trong các giải pháp được cung cấp.
- Sử dụng Binary Search để tìm chênh lệch tối thiểu.
- Với mỗi chênh lệch
mid, ta chỉ cần thử các giá trịLmàLlà độ cao của một ô bất kỳ trong lưới. - Tại sao? Vì nếu có một đường đi với chênh lệch
mid, ta luôn có thể hạ thấpLxuống độ cao của một ô nào đó trên đường đi mà không làm tăng chênh lệch. - Tuy nhiên, giải pháp này vẫn chậm vì số lượng
Lcó thể lên tới N^2. - Giải pháp tối ưu nhất (thường thấy trong các bài thi) là Binary Search + BFS, và khi kiểm tra
mid, ta chỉ cần thử cácLlà độ cao của ô (1,1) hoặc các độ cao nhỏ hơn một lượngmid. - Đoạn code trên vẫn duyệt qua
heights(tất cả các độ cao), về cơ bản là O(N^2 * N^2) nhưng thực tế nếuNnhỏ (như trong kỳ thi THPT) thì có thể chấp nhận được.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(mx^2 * N^2) ~ O(200^2 * N^2) | O(N^2) | Thử tất cả các khoảng độ cao (Brute Force) |
| 2 | O(log(200) * 200 * N^2) ~ O(200 * N^2) | O(N^2) | Tối ưu bằng Binary Search trên chênh lệch |
| 3 | O(N^2 * log(200) * (N^2 + N^2)) ~ O(N^4 log H) | O(N^2) | Tối ưu bằng Binary Search và chỉ thử L là độ cao ô đầu hoặc các ô kề |
Bài học kinh nghiệm
- Bài toán có thể coi là tìm đường đi với ràng buộc về khoảng giá trị (Range). Ta cần tìm khoảng [L, R] sao cho R-L nhỏ nhất mà vẫn có đường đi.
- Sử dụng Binary Search trên kết quả (chênh lệch độ cao) là kỹ thuật tối ưu hóa quan trọng, biến bài toán từ O(K^2 * N^2) thành O(log(K) * N^2 * K') hoặc O(log(K) * N^2 * (N^2)).
- Với mỗi giá trị chênh lệch
diff, ta cần kiểm tra sự t tồn tại của đường đi. Việc kiểm tra này có thể thực hiện bằng cách thử tất cả các mứcLhợp lệ (trong khoảng minheight đến maxheight - diff) và chạy BFS/DFS.
Lỗi thường gặp
- Quên kiểm tra điều kiện ô đầu (1,1) và ô cuối (N,N) có nằm trong khoảng [L, R] hay không trước khi chạy BFS.
- Sử dụng DFS thay cho BFS có thể gây tràn bộ nhớ đệ quy hoặc chạy chậm hơn trong một số trường hợp, mặc dù cả hai đều đúng.
- Lỗi index: Trong các giải pháp mẫu, có sự mix giữa index 0-based và 1-based (Solution 1 dùng 0-based, Solution 3 dùng 1-based). Cần thống nhất index khi viết code.
- Biến
visitedcần được reset cho mỗi lần gọi BFS/DFS.
Bình luận