比赛 |
EYOI与SBOI开学欢乐赛1st |
评测结果 |
AAAAAAAAAA |
题目名称 |
拖拉机 |
最终得分 |
100 |
用户昵称 |
lihaoze |
运行时间 |
0.447 s |
代码语言 |
C++ |
内存使用 |
6.61 MiB |
提交时间 |
2022-08-29 19:58:47 |
显示代码纯文本
#include <bits/stdc++.h>
struct P { int x, y, cnt; };
const int N = 50010, M = 1010;
P a[N];
bool g[M][M], st[M][M];
int n, ans = 1e9, mx, my;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
bool valid(int x, int y) {
return x >= 1 && x <= mx && y >= 1 && y <= my;
}
void bfs() {
std::queue<P> q;
q.push(a[0]);
while (q.size()) {
P now = q.front(); q.pop();
for (int i = 0; i < 4; ++ i) {
int x = now.x + dx[i],
y = now.y + dy[i],
cnt = now.cnt;
if (!valid(x, y))
ans = std::min(ans, cnt);
else if (g[x][y] && !st[x][y] && cnt + 1 < ans)
q.push((P){x, y, cnt + 1}),
st[x][y] = true;
else if (!g[x][y] && !st[x][y] && cnt < ans)
q.push((P){x, y, cnt}),
st[x][y] = true;
}
}
}
int main() {
freopen("tractor.in", "r", stdin);
freopen("tractor.out", "w", stdout);
std::cin >> n >> a[0].x >> a[0].y, a[0].cnt = 0;
for (int i = 1; i <= n; ++ i) {
int x, y; std::cin >> x >> y;
mx = std::max(mx, x);
my = std::max(my, y);
g[x][y] = true;
}
bfs();
std::cout << ans << '\n';
return 0;
}