比赛 |
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;
}