双端队列BFS
注意实现的时候记得把边界扩大到$x\in[0,1001],y\in[0,1001]$
因为可以绕出$[1,1000]$走到$(0,0)$
然后把有干草堆的地方看成边权为$1$,没干草堆的地方看成边权为$0$
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1100;
int dis[N][N];
bool st[N][N];
bool vis[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
deque<PII>q;
int main()
{
int n,sx,sy;
cin>>n>>sx>>sy;
for(int i=0;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
vis[x][y]=true;
}
memset(dis,0x3f,sizeof dis);
dis[sx][sy]=0;
q.push_back({sx,sy});
while(q.size()){
auto [x,y]=q.front();
q.pop_front();
if(st[x][y])continue;
st[x][y]=true;
for(int i=0;i<4;i++){
int ux=x+dx[i],uy=y+dy[i];
if(ux<0||ux>N-1||uy<0||uy>N-1)continue;
int w=vis[ux][uy];
if(dis[ux][uy]>dis[x][y]+w){
dis[ux][uy]=dis[x][y]+w;
if(w)q.push_back({ux,uy});
else q.push_front({ux,uy});
}
}
}
cout<<dis[0][0]<<endl;
return 0;
}