HSG THPT TPHCM 2021 - Tìm đường
Xem dạng PDF
Bạn An đang đứng ở vị trí có tọa độ ~(1,1)~ trên bản đồ và muốn đi đến thành phố ByteCity ở tọa độ ~(N,N)~.
Đây là bản đồ hình vuông, bản đồ có chứa các độ cao ~A[i][j]~ tại mỗi tọa độ ~(i,j)~. Bạn An chỉ đi được từ một ô sang các ô kề cạnh.
Yêu cầu: Bạn An không giỏi leo lên (hoặc xuống) đồi nên muốn nhờ bạn lập trình tìm con đường sao cho độ lệch lớn nhất của độ cao hai ô kề cạnh là nhỏ nhất có thể được. Độ lệch của độ cao hai ô được hiểu là trị tuyệt đối của hiệu độ cao của hai ô này.
Input
Dòng đầu tiên ghi hai số nguyên dương ~N~ ~(1 < N \le 500)~
~N~ dòng tiếp theo, mỗi dòng ghi ~N~ số nguyên dương ~A[i][j]~ cho biết độ cao của các vị trí tương ứng tại dòng i và cột j trên bản đồ ~(0 \le A[i][j] \le 10^6)~
Output
Một số nguyên dương duy nhất cho biết độ lệch lớn nhất của độ cao hai ô kề cạnh trên con đường tìm được.
Sample Input 1
4
3 5 7 7
2 4 4 7
3 3 5 4
9 5 8 5
Sample Output 1
1
Bình luận
anh em tôi có 2 kiểu đây là dùng bin+bfs
include <bits/stdc++.h> using namespace std;
const int MAX = 505; const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int a[MAX][MAX], n; bool canReach(int maxdiff) { queue<pair> q; bool visited[MAX][MAX] = {}; 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; // Đến đích for (int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 1 || ny < 1 || nx > n || ny > n || visited[nx][ny]) continue; if (abs(a[x][y] - a[nx][ny]) <= maxdiff) { visited[nx][ny] = true; q.push({nx, ny}); } } } return false; // Không đến được } int main() { ios::syncwithstdio(false); cin.tie(NULL); cin >> n; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j]; int l = 0, r = 1e9, res = -1; while (l <= r) { int mid = (l + r) / 2; if (canReach(mid)) { res = mid; r = mid - 1; // Tìm độ lệch nhỏ hơn } else { l = mid + 1; } } cout << res << '\n'; return 0; }
nên spoil nhé
đây là dijkstra cho ai cần
include <bits/stdc++.h> using namespace std;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int a[505][505], n; int d[505][505];
int main() { iosbase::syncwithstdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j], d[i][j] = 1e9; priorityqueue<tuple,vector<tuple>, greater<>> pq; d[1][1] = 0; pq.emplace(0, 1, 1); while (!pq.empty()) { auto [maxdiff, x, y] = pq.top(); pq.pop(); if (d[x][y] < maxdiff) continue; for (int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 1 || ny < 1 || nx > n || ny > n) continue; int lech = abs(a[nx][ny] - a[x][y]); int newmax = max(maxdiff, lech); if (newmax < d[nx][ny]) { d[nx][ny] = newmax; pq.emplace(new_max, nx, ny); } } } cout << d[n][n] << '\n'; return 0; }
Có ai hỏi ko ông?
:((
có phải tôi là ng duy nhất ko hiểu đề bài ko
Mình thấy mọi người đa số dùng cách tknp, theo mình thấy thì dijkstra cũng khả thi nhỉ
bfs thoi cung duoc roi, dijkstra nlogn lan
bài này chặt nhị chặt phân kq tìm khoảng cách r dfs hay bfs xem thử khoảng cách có phù hợp k xong lưu biến res
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bài này hay (ko spam)
mà khó quá. anh chi em ý tưởng cái đi
Spoiler
tìm kiếm nhị phân ra X bằng cách nào v ạ
Cho mình hỏi, mình bfs như thế nào để tìm ra các đường đi từ (1;1) đến (n;n) với ạ
giả sử bạn ở vị trí i,j thì có nghĩa tồn tại đường đi từ 1,1 đến vị trí i,j có độ lệch lớn nhất đường <=X nên ta cần bfs từ đỉnh i,j đến các đỉnh kề nó chưa thăm và thỏa mãn độ lệch <=X. Nếu sau khi bfs mà ô n,n được thăm thì có nghĩa là tồn tại đường đi từ 1,1, đến n,n thỏa mãn độ lệch lớn nhất đường <=X và nếu thế ta sẽ giảm X xuống để tìm X cực tiểu. Ngược lại tăng X lên để tìm X.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.