Jennie

这东西叫01BFS

为了省事，我们决定每次把推了干草堆的放后面，没推的放前面。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<deque>
#include<algorithm>
using namespace std;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int n;
bool ma[1005][1005];
struct po{
    int x;
    int y;
}tem;
deque<po> q;
int x,y;
int sx;int sy;
int ans[1007][1007];
int mx[4]={0,0,-1,1};
int my[4]={1,-1,0,0};
int main(){
    read(n);read(sx);read(sy);
    for(int i=1;i<=n;++i){
        read(x);read(y);
        ma[x][y]=1;
    }
    q.push_front((po){
        sx,sy
    });
    memset(ans,-1,sizeof(ans));
    ans[sx][sy]=0;
    while(!q.empty()){
        tem=q.front();
        q.pop_front();
        for(int i=0;i<=3;++i){
            int tx=tem.x+mx[i];
            int ty=tem.y+my[i];
            if(ans[tx][ty]!=-1){
                continue;
            }
            if(tx<0||ty<0||tx>1005||ty>1005){
                continue;
            }
            ans[tx][ty]=ans[tem.x][tem.y]+ma[tx][ty];
            if(ma[tx][ty]){
                q.push_back((po){tx,ty});
            }else{
                q.push_front((po){tx,ty});
            }
        }
    }
    cout<<ans[0][0];
    return 0;
}