题解 P6233 【[eJOI2019]Awesome Arrowland Adventure】

为什么题解都用的是Dijkstra或是SPFA呀……你就没有考虑到毒瘤出题人如果把数据加强到$5000\times5000$该怎么过吗…… 这里介绍一种可以通过上述数据范围的方法：**双端队列bfs**或者叫**01bfs**，[经典例题](https://www.luogu.com.cn/problem/P4667)。 这个方法适用于当一张图中所有的边的边权都是$0$或$1$的图上的最短路。具体而言，我们用**双端队列**替代常规图（即边权均为$1$的图）中的**普通队列**，当遇到$0$边时，从队首入队；当遇到$1$边时，从队尾入队。这样就保证了队列中的距离始终是**单调**的，因而也可以看作是用双端队列替代了Dijkstra中的**优先队列**。显然，因为使用了双端队列，复杂度是$O(n+m)$而非Dijkstra的$O(n+m\log m)$，其中$n$为图中点数，$m$为图中边数。 对于这题而言，我们可以将一个方格拆成$4$个点，分别表示当该方格上的箭头指向$4$个方向时的值，则所有的边权都为$0$或$1$，其中$1$边当且仅当箭头旋转时存在。直接套用上文所述01bfs，即可在$O(nm)$时间内通过本题。 代码： ```cpp #include<bits/stdc++.h> using namespace std; int n,m,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},lim; struct node{ int x,y,z,dir; node(int a,int b,int c,int d){x=a,y=b,z=c,dir=d;} }; char g[510][510]; int dir(char x){ if(x=='N')return 0; if(x=='E')return 1; if(x=='S')return 2; if(x=='W')return 3; return 4; } bool vis[510][510][5]; bool che(node i){ return i.x<=n&&i.x>=1&&i.y<=m&&i.y>=1&&(g[i.x][i.y]!='X'||(i.x==n&&i.y==m))&&!vis[i.x][i.y][i.dir]; } int bfs(){ deque<node>q; q.push_back(node(1,1,0,dir(g[1][1]))); while(!q.empty()){ node x=q.front();q.pop_front(); if(!che(x))continue;vis[x.x][x.y][x.dir]=true; if(x.x==n&&x.y==m)return x.z; q.push_front(node(x.x+dx[x.dir],x.y+dy[x.dir],x.z,dir(g[x.x+dx[x.dir]][x.y+dy[x.dir]]))); q.push_back(node(x.x,x.y,x.z+1,(x.dir+1)%4)); } return -1; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%s",g[i]+1); if(g[1][1]=='X'&&(n>1||m>1)){puts("-1");return 0;} printf("%d\n",bfs()); return 0; } ```