Hướng dẫn giải của Kiến
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
Kiến đi từ ô ~(0,0)~ sang 4 ô kề, tránh vật cản, tối đa ~S~ bước; đếm số ô kiến đến được. Khoảng cách ngắn nhất là bài toán BFS trên lưới, khó ở chỗ ~S~ lên tới ~10^7~ nên không thể lập hết lưới.
Sub 1: BFS trực tiếp — dùng khi ~S \le 1000~
Vì kiến chỉ đi xa nhất ~S~ ô theo mỗi hướng nên chỉ cần lưới ~(2S+1) \times (2S+1)~ (tối đa khoảng 4 triệu ô). BFS từ ~(0,0)~, dừng ở độ sâu ~S~, đếm số ô đã đến. Nếu chỉ nộp sub này: đúng 14/20 test.
Sub 2: BFS trong hình vuông chứa vật cản + công thức phần ngoài — ~O(10^6)~
Mọi vật cản nằm trong ~|x|,|y| \le 1000~ nên hàng ngoài cùng ~|x| = 1001~, ~|y| = 1001~ không có vật cản. BFS (không giới hạn ~S~) trong hình vuông ~[-1001, 1001]^2~ để biết khoảng cách ~D~ của từng ô. Phần lưới ngoài hình vuông là đất trống: ô cách viền ~t~ bước theo hướng ra ngoài có khoảng cách ~D_{viền} + t~ (vì đi dọc viền không bao giờ thiệt hơn). Do đó mỗi ô viền (không tính góc) có ~D < S~ đóng góp thêm ~S - D~ ô ngoài theo tia đi ra, và mỗi góc có ~D~ đóng góp ~(T-1)T/2~ ô với ~T = S - D~ (các ô lệch cả hai hướng). Cộng với số ô trong hình vuông có ~D \le S~. Đáp án cỡ ~S^2~ nên dùng long long. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu (đọc/ghi file ANT.INP/ANT.OUT); nếu ~S \le 1000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Kết quả: 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int C, S;
int ox[10005], oy[10005];
const int R = 1001; // mọi vật cản có |x|,|y| <= 1000, hàng ngoài cùng |x|=1001 hoàn toàn trống
const int W = 2 * R + 1;
static int D[W][W]; // khoảng cách ngắn nhất (-1: chưa tới / không tới được)
static bool blk[W][W];
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
// BFS từ (0,0) trên hình vuông [-lim, lim]^2, chỉ đi tối đa maxd bước; trả về số ô đã đến
long long bfs(int lim, long long maxd) {
for (int i = 0; i < W; i++) for (int j = 0; j < W; j++) D[i][j] = -1;
queue<pair<int,int>> q;
D[R][R] = 0; q.push({R, R});
long long cnt = 0;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
cnt++;
if (D[x][y] >= maxd) continue;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (abs(nx - R) > lim || abs(ny - R) > lim) continue;
if (blk[nx][ny] || D[nx][ny] != -1) continue;
D[nx][ny] = D[x][y] + 1;
q.push({nx, ny});
}
}
return cnt;
}
// Sub 1: BFS trực tiếp, chỉ dùng khi S <= 1000 (kiến không ra khỏi hình vuông cạnh 2S+1 <= W)
void sub1() {
cout << bfs(min(S, R), S) << "\n";
}
// Sub 2: BFS trong hình vuông [-1001,1001]^2 (không giới hạn S), phần ngoài hình vuông là
// đất trống nên tính bằng công thức theo khoảng cách của các ô trên viền.
void sub2() {
bfs(R, (long long)4e18);
long long ans = 0;
for (int i = 0; i < W; i++) for (int j = 0; j < W; j++)
if (D[i][j] != -1 && D[i][j] <= S) ans++;
// Ô ngoài hình vuông cách viền t bước theo hướng ra ngoài có khoảng cách D(viền)+t
for (int t = 0; t < W; t++) {
int e[4] = {D[W - 1][t], D[0][t], D[t][W - 1], D[t][0]};
for (int k = 0; k < 4; k++)
if (e[k] != -1 && e[k] < S) ans += S - e[k];
}
// bốn góc: các ô (a,b) với a,b >= 1 lệch khỏi góc
int cs[4][2] = {{0, 0}, {0, W - 1}, {W - 1, 0}, {W - 1, W - 1}};
for (auto& c : cs) {
long long d = D[c[0]][c[1]];
if (d == -1) continue;
long long T = S - d;
if (T >= 2) ans += (T - 1) * T / 2;
}
cout << ans << "\n";
}
int main() {
freopen("ANT.INP", "r", stdin);
freopen("ANT.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> C >> S;
for (int i = 0; i < C; i++) {
cin >> ox[i] >> oy[i];
blk[ox[i] + R][oy[i] + R] = true;
}
blk[R][R] = false;
if (S <= 1000) sub1();
else sub2();
return 0;
}
Bình luận