题解【P6233 [eJOI2019]Awesome Arrowland Adventure】

Lice · 2020-03-22 13:56:27 · 题解

Description

它 spfa 了

Solution

显然直接胡乱转是行不通的。

然而正解是图论中的最短路。

那样例1来说：

EES
SSW
ESX

假如你现在要从 (0,1) 走到 (1,1)，的话，如果不绕圈子，那么我们需要将位置 (0,1) 的箭头旋转一次，然后就可以走过去了。这可以抽象成： 从顶点 (0,1) 有一条到 (1,1) 的边，边权为1。其他的位置同理，以位置之间移动的所需旋转次数为边权 。如果是 X 的话，就把它的所有出边边权设成 inf 。

那么对这个箭头矩阵进行这样的转化之后，我们得到了一张这样的图：

然后？直接跑最短路就好啦！

下面用了 Dijkstra 算法，spfa 应该可以（这个坑留个下一个题解）。

Code

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
const char dir[]="WENS";

int val[256];
const int N=502;
char s[N][N];
int dist[N][N];
bool book[N][N];
int n,m;

int cost(char a,char b)//计算字符（箭头）转化的花费
{
    int sub=val[(int)b]-val[(int)a];
    if(sub<0) sub+=4;
    return sub;
}

struct HeapNode
{
    int x,y,dis;
    HeapNode(int _x,int _y,int _d):x(_x),y(_y),dis(_d){}
    bool operator <(const HeapNode &t)const{return dis>t.dis;}
};

bool out_of_range(int x,int y)
{
    return (x<1||y<1||x>n||y>m);
}

void SSSP()//建不建图其实无所谓，可以直接在原矩阵上跑。但是建图的话就可以直接套板子了，少了一些判断。
{//堆优化 Dijkstra 板子
    priority_queue<HeapNode> Q;
    Q.push(HeapNode(1,1,dist[1][1]=0));
    while(!Q.empty())
    {
        int x=Q.top().x,y=Q.top().y;
        Q.pop();
        if(book[x][y]) continue;
        book[x][y]=true;
        if(s[x][y]=='X') continue;
        for(register int i=0;i<4;i++)
        {
            HeapNode nxt(x+dx[i],y+dy[i],dist[x][y]+cost(s[x][y],dir[i]));
            if(out_of_range(nxt.x,nxt.y)) continue;
            if(dist[nxt.x][nxt.y]<=nxt.dis) continue;
            dist[nxt.x][nxt.y]=nxt.dis;
            Q.push(HeapNode(nxt));
        }
    }
}

signed main()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++)
        scanf("%s",s[i]+1);

    memset(dist,0x3f,sizeof dist);
    memset(book,false,sizeof book);
    val['W']=0,val['N']=1;
    val['E']=2,val['S']=3;

    SSSP();
    printf("%d\n",dist[n][m]==0x3f3f3f3f?-1:dist[n][m]);
    return 0;
}

应该是第一篇题解，如果帮到了你不妨点个赞啊 awa