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