题解 P6233 【[eJOI2019]Awesome Arrowland Adventure】

xtx1092515503 · 2020-06-03 18:23:53 · 题解

为什么题解都用的是Dijkstra或是SPFA呀……你就没有考虑到毒瘤出题人如果把数据加强到5000\times5000该怎么过吗……

这里介绍一种可以通过上述数据范围的方法：双端队列bfs或者叫01bfs，经典例题。

这个方法适用于当一张图中所有的边的边权都是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)时间内通过本题。

代码：

#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;
}