记录编号	575244	评测结果	AAAAAAAAAA
题目名称	[USACO Mar12] 拖拉机	最终得分	100
用户昵称	Skloud	是否通过	通过
代码语言	C++	运行时间	0.266 s
提交时间	2022-09-07 21:24:58	内存使用	6.37 MiB

#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream fin("tractor.in");
ofstream fout("tractor.out");
struct node{
    int x,y,cnt;
    node(){}
    node(int a,int b,int c){x=a,y=b,cnt=c;}
};
int n,x,y,maxx,maxy;
int ans=500000;
int a,b;
int ma[5]={1,0,-1,0},mb[5]={0,1,0,-1};
bool f[1005][1005],g[1005][1005];
deque <node> q;
inline bool islow(int x,int y)
{
    return x>=1&&y>=1&&x<=maxx&&y<=maxy;
}
void bfs()
{
    q.push_back(node(x,y,0));
    while(!q.empty())
    {
        node t=q.front();
        q.pop_front();
        for(int i=0;i<4;i++)
        {
            a=t.x+ma[i],b=t.y+mb[i];
            if(!islow(a,b))
            {
                ans=min(ans,t.cnt);
                continue;
            } 
            if(f[a][b]) continue;
            if(g[a][b]&&t.cnt+1<ans)
            {
                q.push_back(node(a,b,t.cnt+1));
                f[a][b]=1;
            }
            else if(!g[a][b]&&t.cnt<ans)
            {
                q.push_front(node(a,b,t.cnt));
                f[a][b]=1;
            }
        }
    }
}
int main()
{
    fin>>n>>x>>y;
    for(int i=1;i<=n;i++)
    {
        fin>>a>>b;
        g[a][b]=1,
        maxx=max(maxx,a),maxy=max(maxy,b);
    }
    bfs();
    fout<<ans<<endl;
    return 0;
}