AC日记——小A和uim之大逃离 II 洛谷七月月赛

小A和uim之大逃离 II

思路：

　　spfa；

代码：

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

struct NodeType

{

    int x,y,k;

    NodeType(int x_,int y_,int k_):x(x_),y(y_),k(k_){}

    NodeType(){}

};

const int dx[]={,-,,,};

const int dy[]={,,,,-};

int n,m,d,r,dis[][][];

char Map[][];

queue<NodeType>que;

bool if_[][][];

int main()

{

    scanf("%d%d%d%d",&n,&m,&d,&r);

    for(int i=;i<=n;i++) scanf("%s",Map[i]+);

    for(int i=;i<=n;i++)

    {

        for(int v=;v<=m;v++) dis[i][v][]=dis[i][v][]=INF;

    }

    dis[][][]=;int x,y,k;que.push(NodeType(,,)),if_[][][]=true;

    NodeType now;

    for(;!que.empty();)

    {

        now=que.front(),que.pop();

        if_[now.x][now.y][now.k]=false,k=now.k;

        for(int i=;i<=;i++)

        {

            x=now.x+dx[i],y=now.y+dy[i];

            if(x>&&x<=n&&y>&&y<=m&&Map[x][y]=='.')

            {

                if(dis[now.x][now.y][k]+<dis[x][y][k])

                {

                    dis[x][y][k]=dis[now.x][now.y][k]+;

                    if(!if_[x][y][k]) if_[x][y][k]=true,que.push(NodeType(x,y,k));

                }

            }

        }

        if(!k)

        {

            x=now.x+d,y=now.y+r;

            if(x>&&x<=n&&y>&&y<=m&&Map[x][y]=='.')

            {

                dis[x][y][]=dis[now.x][now.y][]+;

                if(!if_[x][y][]) if_[x][y][],que.push(NodeType(x,y,));

            }

        }

    }

    if(dis[n][m][]==INF&&dis[n][m][]==INF) printf("-1\n");

    else printf("%d\n",min(dis[n][m][],dis[n][m][]));

    return ;

}