比赛 |
EYOI与SBOI开学欢乐赛1st |
评测结果 |
AWTTTTWTTT |
题目名称 |
拖拉机 |
最终得分 |
10 |
用户昵称 |
Skloud |
运行时间 |
7.628 s |
代码语言 |
C++ |
内存使用 |
8.02 MiB |
提交时间 |
2022-08-29 20:44:46 |
显示代码纯文本
#include<iostream>
#include<fstream>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
ifstream fin("tractor.in");
ofstream fout("tractor.out");
struct node{
int x,y;
node(){};
node(int a,int b)
{
x=a,y=b;
}
};
queue <node> q;
vector <node> v[3];
int n,x,y,a[1005][1005],c,b;
int maxx=0,maxy=0;
void bfs(node u,int f)
{
q.push(u);
a[u.x][u.y]=f;
v[f].push_back(u);
while(!q.empty())
{
int x=q.front().x,y=q.front().y;
q.pop();
if(a[x+1][y]==0&&x+1<=maxx){
a[x+1][y]=f;
q.push(node(x+1,y));
v[f].push_back(node(x+1,y));
}
if(x-1>=0&&a[x-1][y]==0){
a[x-1][y]=f;
q.push(node(x-1,y));
v[f].push_back(node(x-1,y));
}
if(a[x][y+1]==0&&y+1<=maxy){
a[x][y+1]=f;
q.push(node(x,y+1));
v[f].push_back(node(x,y+1));
}
if(y-1>=0&&a[x][y-1]==0){
a[x][y-1]=f;
q.push(node(x,y-1));
v[f].push_back(node(x,y-1));
}
}
}
int main()
{
fin>>n>>x>>y;
int ans=0x3fffffff;
for(int i=1;i<=n;i++)
{
fin>>c>>b;
a[c][b]=-1;
maxx=max(maxx,c);
maxy=max(maxy,b);
}
maxx++;
maxy++;
bfs(node(x,y),1);
bfs(node(1,1),2);
// for(int i=0;i<=maxx;i++)
// {
// for(int j=0;j<=maxy;j++)
// {
// cout<<a[i][j]<<' ';
// }
// cout<<endl;
// }
for(int i=0;i<v[1].size();i++)
{
for(int j=0;j<v[2].size();j++)
{
// cout<<v[1][i].x<<' '<<v[1][i].y<<' ';
// cout<<v[2][j].x<<' '<<v[2][j].y<<endl;
ans=min(ans,abs(v[1][i].x-v[2][j].x)+abs(v[1][i].y-v[2][j].y)-1);
}
}
fout<<ans<<endl;
return 0;
}