比赛 EYOI与SBOI开学欢乐赛1st 评测结果 AATTTTTATT
题目名称 拖拉机 最终得分 30
用户昵称 遥时_彼方 运行时间 7.026 s
代码语言 C++ 内存使用 13.42 MiB
提交时间 2022-08-29 20:01:21
显示代码纯文本
#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
} 
inline void write(int x)
{
	if(x<0) {x=~(x-1);putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
///////////////////////////////////////
const int N=1e3+50;
const int M=5e4+50;
struct G
{
	int kd;
	int dep;
}a[N][N];
int nc;
int bx,by;
struct G2{int x,y;} f[2][M];//滚动数组
int fs[2];//fs为数量 
inline int IF(int x,int y,int dep,int ex)
{
	int re=0;
	if(!a[x][y].dep)
	{
		a[x][y].dep=dep+a[x][y].kd;
		re=1;
		if(a[x][y].kd)
		{
			f[ex][++fs[ex]].x=x;
			f[ex][fs[ex]].y=y;
			re=0;
		}
	}
	return re;
}
void bfs(int ex,int x,int y)
{
	if(x==0||x==1000||y==0||y==1000) a[0][0].dep=a[x][y].dep;
	if(x!=0&&IF(x-1,y,a[x][y].dep,ex)) f[ex^1][++fs[ex^1]].x=x-1,f[ex^1][fs[ex^1]].y=y;
	if(x!=1000&&IF(x+1,y,a[x][y].dep,ex)) f[ex^1][++fs[ex^1]].x=x+1,f[ex^1][fs[ex^1]].y=y;
	if(y!=0&&IF(x,y-1,a[x][y].dep,ex)) f[ex^1][++fs[ex^1]].x=x,f[ex^1][fs[ex^1]].y=y-1;
	if(y!=1000&&IF(x,y+1,a[x][y].dep,ex)) f[ex^1][++fs[ex^1]].x=x,f[ex^1][fs[ex^1]].y=y+1;
	return;
}
int main()
{
    freopen("tractor.in","r",stdin);
	freopen("tractor.out","w",stdout);
    nc=read();
    bx=read(),by=read();
    int s1,s2;
    rep(i,1,nc) s1=read(),s2=read(),a[s1][s2].kd=1;
    f[1][1].x=bx,f[1][1].y=by,fs[1]=1;
    a[bx][by].dep=1;
    for(int i=0;!a[0][0].dep;i^=1)
    {
    	fs[i]=0;
    	rep(o,1,fs[i^1])
    	{
    		bfs(i,f[i^1][o].x,f[i^1][o].y);
//    		cout<<"p2:"<<f[i^1][o].x<<" "<<f[i^1][o].y<<endl;
		}
//		cout<<"p3"<<endl;
	}
	a[0][0].dep+=a[0][0].kd-1;
	cout<<a[0][0].dep<<endl;
    return 0;
}