abc_387_d 题解

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN=1100;
int h,w;
int stx,sty,edx,edy;
string a[MAXN];
bool vis[MAXN][MAXN][2];
int dx[4]={1,-1,0,0}; 
int dy[4]={0,0,1,-1};
struct Node{
    int x,y,dep,dir;//(x, y, 步数, 移动方向)
};
bool cz(int dir){//垂直 0 
    return dir==0;
}
bool sp(int dir){//水平 1 
    return dir==1;
}
queue<Node>q;
int bfs(int stx,int sty,int edx,int edy) {
	memset(vis,0,sizeof(vis));
    //初始状态可以选择水平或垂直
    vis[stx][sty][0]=1;//假设从垂直方向开始
    vis[stx][sty][1]=1;//假设从水平方向开始
    q.push({stx,sty,0,0}); //从垂直开始
    q.push({stx,sty,0,1}); //从水平开始
    while(!q.empty()) {
        Node t=q.front();
        q.pop();
        if(t.x==edx&&t.y==edy)return t.dep;
        int ndir=(t.dir==0)?1:0;//如果当前是垂直,下一步必须是水平
        for(int i=0;i<4;i++){
            int xx=t.x+dx[i];
            int yy=t.y+dy[i];
            if (xx>=0&&xx<h&&yy>=0&&yy<w&&a[xx][yy]!='#')
                if((cz(t.dir)&&(i==2||i==3))||(sp(t.dir)&&(i==0||i==1))){
                    if(!vis[xx][yy][ndir]){
                        vis[xx][yy][ndir]=1;
                        q.push({xx,yy,t.dep+1,ndir});
                    }
                }
        }
    }
    return -1;
}
int main() {
    cin>>h>>w;
    for(int i=0;i<h;i++){
        cin>>a[i];
        for(int j=0;j<w;j++){
            if(a[i][j]=='S'){
                stx=i;
                sty=j;
            } 
			else if(a[i][j]=='G'){
                edx=i;
                edy=j;
            }
        }
    }
    int ans=bfs(stx,sty,edx,edy);
    cout<<ans<<endl;
    return 0;
}