题解 P3818 【小A和uim之大逃离 II】

· · 题解

一道简单的裸BFS啊~（貌似比I要简单？好吧I我还没做）

如果没有药水这个限制就是裸的BFS走迷宫，当然处理药水也很简单。

原先走迷宫需要用一个数组step[x][y]来记录到(x,y)的最少步数，这里只需要再添加一维就可以了。

我们用step[x][y][0]表示走到(x,y)且没有喝药的最少步数，用step[x][y][1]表示走到(x,y)且已经喝药的最小步数。

因为根据题目要求，总共只能喝一次药，所以简单处理一下即可。

具体过程如下：

遍历到一个点（简称遍历点），枚举上下左右的点（简称到达点），如果到达点可行，先把到达点按走迷宫的方式处理了，然后看遍历点状态是否吃药，如果未吃药则再处理到达点吃药可转移的点，当然要注意第三维的变化。

由于过程已经叙述过了故程序就不再注释。建议先根据上述思路自己写写代码哦！

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1005;
int h,w,d,r,st[N][N][2];
char s[N][N];
struct Point
{
    int x,y,u;
};
queue<Point> Q;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool check(int x, int y)
{
    return x>=1&&y>=1&&x<=h&&y<=w&&s[x][y]=='.';
}
int main()
{
    scanf("%d%d%d%d",&h,&w,&d,&r);
    for(int i=1;i<=h;i++)
        scanf("%s",s[i]+1);
    memset(st,-1,sizeof(st));
    st[1][1][0]=0;
    Q.push((Point){1,1,0});
    while(!Q.empty()&&st[h][w][0]==-1&&st[h][w][1]==-1)
    {
        Point f=Q.front();
        Q.pop();
        for(int i=0;i<4;i++)
        {
            int x=dx[i]+f.x,y=dy[i]+f.y;
            if(check(x,y)&&st[x][y][f.u]==-1)
            {
                Q.push((Point){x,y,f.u});
                st[x][y][f.u]=st[f.x][f.y][f.u]+1;
                if(f.u==0&&check(x+d,y+r)&&st[x+d][y+r][1]==-1)
                {
                    Q.push((Point){x+d,y+r,1});
                    st[x+d][y+r][1]=st[x][y][0]+1;
                }
            }
        }
    }
    if(st[h][w][0]==-1&&st[h][w][1]==-1) puts("-1");
    else 
    printf("%d",min(st[h][w][0]==-1?1<<30:st[h][w][0],
                    st[h][w][1]==-1?1<<30:st[h][w][1])); //奇葩的写法，不建议效仿QWQ
}

PS当时比赛没时间写题啊 要写作业QAQ