记录编号	37517	评测结果	AAAAAAAAAA
题目名称	[USACO Mar12] 拖拉机	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.101 s
提交时间	2012-03-31 12:13:02	内存使用	2.26 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<deque>

using namespace std;

const int wz[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int oo=~0u>>1;

struct Node 
{
	int x,y,cost;
	Node(int _x,int _y,int _cost):x(_x),y(_y),cost(_cost){}
};

int N,X,Y,ans=oo,mx,my;
bool vis[1010][1010],Map[1010][1010];

void bfs()
{
	deque<Node>deq;
	deq.push_back(Node(X,Y,0));
	while(!deq.empty())
	{
		for(int i=0;i<4;i++)
		{
			int x=deq.front().x+wz[i][0],y=deq.front().y+wz[i][1],cost=deq.front().cost;
			if(x<1||y<1||x>mx||y>my)
				ans=min(ans,cost);
			else if(Map[x][y]&&!vis[x][y]&&cost+1<ans)
			{
				vis[x][y]=true;
				deq.push_back(Node(x,y,cost+1));
			}
			else if(!Map[x][y]&&!vis[x][y]&&cost<ans)
			{
				vis[x][y]=true;
				deq.push_back(Node(x,y,cost));
			}
		}
		deq.pop_front();
	}
}

int main()
{
	freopen("tractor.in","r",stdin);
	freopen("tractor.out","w",stdout);
	scanf("%d%d%d",&N,&X,&Y);
	for(int i=1;i<=N;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		mx=max(mx,x);
		my=max(my,y);
		Map[x][y]=true;
	}
	bfs();
	printf("%d\n",ans);
	return 0;
}