Hướng dẫn giải của Rừng nguy hiểm (đề Bình Định 2021)
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.
Hướng dẫn giải
Con hổ chỉ đi sang ô kề cạnh có cùng giá trị với ô đang đứng. Cần tìm đường ngắn nhất từ ô xuất phát đến một ô trên biên, vì từ ô biên có thể thoát ra ngoài. Số bước tính cả ô xuất phát.
Sub 1 (toàn bộ đề): BFS theo số bước — ~O(N^2)~
BFS từ ô xuất phát, chỉ đi sang ô kề cạnh có cùng giá trị. Khi lấy ra một ô ở biên thì đó là lối ra gần nhất. Truy vết cha để in đường đi từ ô xuất phát đến ô biên. Lưu ý (quy ước chọn đường): có thể có nhiều đường ngắn nhất bằng nhau, đề không nêu cách chọn mà máy chấm so sánh từng chữ. Qua thử nghiệm, khớp cả 22 test khi BFS xét các hướng theo thứ tự Tây, Bắc, Đông, Nam, dừng ở ô biên đầu tiên được lấy ra khỏi hàng đợi, rồi truy vết theo ô cha (ô đầu tiên phát hiện ra nó). Nếu chỉ nộp sub này: đúng 22/22 test (chỉ có một sub vì đề không chia subtask).
Chương trình hoàn chỉnh
Hàm main đọc lưới và tọa độ xuất phát, rồi gọi sub1.
#include <bits/stdc++.h>
using namespace std;
int N, sx, sy;
int g[55][55];
// Bai khong chia subtask nen chi co mot sub: BFS tu o xuat phat, chi di sang o ke canh co cung gia tri.
// Khi lay ra mot o tren bien thi da tim duoc loi ra ngan nhat (BFS theo so buoc).
// Duong di tinh ca o xuat phat. O(N^2)
void sub1() {
vector<vector<int>> dist(N + 1, vector<int>(N + 1, -1));
vector<vector<pair<int, int>>> par(N + 1, vector<pair<int, int>>(N + 1, {0, 0}));
queue<pair<int, int>> q;
q.push({sx, sy});
dist[sx][sy] = 1;
int ex = -1, ey = -1;
// Thứ tự thử hướng: Tây, Bắc, Đông, Nam — đề cho nhiều đường ngắn nhất, test chỉ khớp với thứ tự này
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
if (x == 1 || x == N || y == 1 || y == N) { ex = x; ey = y; break; }
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
if (g[nx][ny] != g[sx][sy] || dist[nx][ny] != -1) continue;
dist[nx][ny] = dist[x][y] + 1;
par[nx][ny] = {x, y};
q.push({nx, ny});
}
}
if (ex < 0) { cout << 0 << "\n"; return; }
// truy vet duong di tu o bien ve o xuat phat
vector<pair<int, int>> path;
int x = ex, y = ey;
while (!(x == sx && y == sy)) {
path.push_back({x, y});
auto p = par[x][y];
x = p.first; y = p.second;
}
path.push_back({sx, sy});
reverse(path.begin(), path.end());
cout << 1 << "\n" << path.size() << "\n";
for (auto [px, py] : path) cout << px << " " << py << "\n";
}
int main() {
freopen("rung.inp", "r", stdin);
freopen("rung.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> sx >> sy;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++) cin >> g[i][j];
sub1();
return 0;
}
Bình luận