题解：ABC387 D - Snaky Walk

· · 题解

思路：

BFS。

如没学过，可以先看看 OI Wiki，然后把模版题 P1443 马的遍历做了。

考虑到题目要求，上一次横着走，那下一次就必须竖着走；上一次竖着走，那下一次就必须横着走，所以 BFS 的队列里的变量要多一个变量 cx 表示上一次走的方向，同时考虑到可能横着走到达这个点不可以到达终点，但是竖着走到达这个点可能可以到达终点，所以标记数组也要多一维，表示方向，当现在到达的点为终点时，说明可以到达输出答案。

其余的就是 BFS 的模版了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int h,w;
int sx,sy,ex,ey;
bool bj[1200][1200][4];
char jz[1200][1200];
struct node{
    int x,y;
    int cx;// 上一次的上下/左右/起点 
    int step;
};
queue<node>dl;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1}; 
int main(){
    cin>>h>>w;
    for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
        cin>>jz[i][j];
        if(jz[i][j]=='S')sx=i,sy=j;
        else if(jz[i][j]=='G')ex=i,ey=j;
        else if(jz[i][j]=='#')bj[i][j][1]=1,bj[i][j][2]=1,bj[i][j][0]=1;
    }
    dl.push({sx,sy,0,0});
    while(dl.empty()==0){
        node tamp=dl.front();dl.pop();
//      cout<<tamp.x<<" "<<tamp.y<<"\n";
        if(tamp.x==ex&&tamp.y==ey){
            cout<<tamp.step;
            return 0;
        }
        if(bj[tamp.x][tamp.y][tamp.cx])continue;
        bj[tamp.x][tamp.y][tamp.cx]=1;
        for(int i=0;i<4;i++){
            int tx=tamp.x+dx[i],ty=tamp.y+dy[i];
            if(tx<1||ty<1||tx>h||ty>w)continue;
            if(i<=1&&tamp.cx!=1){
                dl.push({tx,ty,1,tamp.step+1});
            }
            else if(i>1&&tamp.cx!=2){
                dl.push({tx,ty,2,tamp.step+1});
            }
        }
    } 
    cout<<-1;
    return 0;
}

AC 记录。