记录编号	575002	评测结果	AAAAAAAAAA
题目名称	[USACO Mar12] 拖拉机	最终得分	100
用户昵称	该账号已注销	是否通过	通过
代码语言	C++	运行时间	1.230 s
提交时间	2022-08-31 19:37:35	内存使用	11.61 MiB

#include<bits/stdc++.h>
using namespace std;
int bx,by,mp[1010][1010],n,mxx,mxy,mnx=0x3f3f3f3f,mny=0x3f3f3f3f,f[1010][1010];
int dx[6]={0,1,0,-1,0},dy[6]={0,0,1,0,-1};
bool v[1010][1010];
deque<pair<int,int> >q;
int bfs(){
    q.push_front(make_pair(bx,by));
    v[bx][by]=1;
    while(!q.empty()){
        int x=q.front().first,y=q.front().second;
        q.pop_front();
        for(int i=1;i<=4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>mxx+1||nx<0||ny>mxy+1||ny<0)continue;
            if(v[nx][ny]==1)continue;
            v[nx][ny]=1;
            if(f[nx][ny]>f[x][y]+mp[nx][ny]){
                f[nx][ny]=f[x][y]+mp[nx][ny];
            }
            if(mp[nx][ny]==0){
                q.push_front(make_pair(nx,ny));
            }
            else{
                q.push_back(make_pair(nx,ny));
            }
        }
    }
    return 0;
}
int main(){
    freopen("tractor.in","r",stdin);
    freopen("tractor.out","w",stdout);
    cin>>n>>bx>>by;
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        mp[x][y]++;
        mxx=max(mxx,x);
        mxy=max(mxy,y);
        mnx=min(mnx,x);
        mny=min(mny,y);
    }
    f[bx][by]=0;
    bfs();
    cout<<f[0][0]+mp[0][0]<<endl;
    return 0;
}