记录编号	574947	评测结果	AAAAAAAAAA
题目名称	[USACO Mar12] 拖拉机	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.082 s
提交时间	2022-08-30 02:14:34	内存使用	6.60 MiB

#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;
}