比赛 EYOI与SBOI开学欢乐赛1st 评测结果 AAAAWAWWWW
题目名称 拖拉机 最终得分 50
用户昵称 op_组撒头屯 运行时间 0.605 s
代码语言 C++ 内存使用 19.54 MiB
提交时间 2022-08-29 19:46:31
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=50000+5;
const int M=1000+5;
const int inf=0x3f3f3f3f;
int n,mxx=0,mxy=0;
int id[M][M]={0},cnt=0,val[M*M];
bool mp[M][M]={0},vis[M][M]={0};
inline void fld(int x,int y,int cnt){
    if (id[x][y]!=0)return ;
    id[x][y]=cnt;
    if (x!=0&&mp[x-1][y]!=1)fld(x-1,y,cnt);
    if (y!=0&&mp[x][y-1]!=1)fld(x,y-1,cnt);
    if (x!=mxx+1&&mp[x+1][y]!=1)fld(x+1,y,cnt);
    if (y!=mxy+1&&mp[x][y+1]!=1)fld(x,y+1,cnt);
    return ;
}
struct sdf{
    int id,cnt;
}fir[M*M];
queue<sdf>q;
stack<int>st;
inline void dfs(int x,int y,int cnt){
    if (vis[x][y]==1)return ;
    vis[x][y]=1;
    if (x!=0){
        if (mp[x-1][y]==1){
            if (val[id[x-2][y]]>cnt){
                st.push(id[x-2][y]);val[id[x-2][y]]=cnt;
            }
        }
        else{
            if (vis[x-1][y]==0)dfs(x-1,y,cnt);
        }
    }
    if (y!=0){
        if (mp[x][y-1]==1){
            if (val[id[x][y-2]]>cnt){
                st.push(id[x][y-2]);val[id[x][y-2]]=cnt;
            }
        }
        else{
            if (vis[x][y-1]==0)dfs(x,y-1,cnt);
        }
    }
    if (x!=mxx+1){
        if (mp[x+1][y]==1){
            if (val[id[x+2][y]]>cnt){
                st.push(id[x+2][y]);val[id[x+2][y]]=cnt;
            }
        }
        else{
            if (vis[x+1][y]==0)dfs(x+1,y,cnt);
        }
    }
    if (y!=mxy+1){
        if (mp[x][y+1]==1){
            if (val[id[x][y+2]]>cnt){
                st.push(id[x][y+2]);val[id[x][y+2]]=cnt;
            }
        }
        else{
            if (vis[x][y+1]==0)dfs(x,y+1,cnt);
        }
    }
}

int main(){
    freopen ("tractor.in","r",stdin);
    freopen ("tractor.out","w",stdout);
    int x,y;
    scanf("%d%d%d",&n,&x,&y);
    for (int i=1;i<=n;i++){
        int a,b;scanf("%d%d",&a,&b);
        mp[a][b]=1;mxx=max(mxx,a);mxy=max(mxy,b);
    }
    bool yes=0;
    if (mp[1][1]==1){
        mp[1][1]=0;yes=1;
    }
    fld(0,0,++cnt);fir[cnt]={0,0};
    for (int i=1;i<=mxx;i++){
        for (int j=1;j<=mxy;j++){
            if (mp[i][j]==0&&id[i][j]==0){
                fld(i,j,++cnt);fir[cnt]={i,j};
            }
        }
    }
    memset(val,0x3f,sizeof(val));
    q.push({id[x][y],0});val[id[x][y]]=0;
    while(!q.empty()){
        sdf t=q.front();q.pop();
        memset(vis,0,sizeof(vis));
        dfs(fir[t.id].id,fir[t.id].cnt,t.cnt+1);
        while(!st.empty()){
            int tmp=st.top();
            q.push({tmp,t.cnt+1});
            st.pop();
        }
        if (val[id[1][1]]!=inf){
            break;
        }
    }
    if (yes==1)val[id[1][1]]++;
    printf("%d\n",val[id[1][1]]);
    return 0;
}