题解：ABC387 D - Snaky Walk

封面

洛谷文章链接

思路：

BFS。

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

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

其余的就是 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 记录。