裸bfs不解释。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m; const int N=505; const int dx[4]={0,1,0,-1}; const int dy[4]={1,0,-1,0}; struct node { int x,y; }q[120000]; int dist[N*2][N*2]; bool bz[N*2][N*2]; int x,y,t,w=1; int main() { memset(dist,-1,sizeof(dist)); scanf("%d%d%d",&x,&y,&n); x+=500; y+=500; fo(i,1,n) { int a,b; scanf("%d%d",&a,&b); bz[a+500][b+500]=1; } q[1].x=500,q[1].y=500,dist[500][500]=0; while (t<w) { int x1=q[++t].x; int y1=q[t].y; fo(k,0,3) { int x2=x1+dx[k]; int y2=y1+dy[k]; if (!bz[x2][y2]&&dist[x2][y2]==-1) { q[++w].x=x2; q[w].y=y2; bz[x2][y2]=1; dist[x2][y2]=dist[x1][y1]+1; if (x2==x&&y2==y) { printf("%d\n",dist[x][y]); return 0; } } } } }