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