AT_abc387_d 题解

ikunTLE · 2025-01-12 06:00:55 · 题解

题目传送门

思路

可以使用 bfs 解决此题。

与普通 bfs 不同，这道题遍历需要横纵交替。于是可以在 bfs 队列中增加一维，表示上一次操作是横还是纵。在下一次进入时，就可以根据队列中新增的一维来判断应该横向走还是纵向走。

bfs 的时间复杂度为 \mathcal{O}(N^2)。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e3+10;
int dx1[]={0,0,0},dy1[]={0,-1,1};
int dx2[]={0,-1,1},dy2[]={0,0,0};
struct node{
    int x,y,flag;
};queue<node>q;
char s[N][N];
bool vis[N][N][2];
signed main(){
    int h=read(),w=read();
    for(int i=1;i<=h;++i)
        scanf("%s",s[i]+1);
    int bx,by,ex,ey;
    for(int i=1;i<=h;++i)
        for(int j=1;j<=w;++j)
            if(s[i][j]=='S')
                bx=i,by=j;
            else if(s[i][j]=='G')
                ex=i,ey=j;
    q.push({bx,by,0}),q.push({bx,by,1});
    vis[bx][by][0]=true,vis[bx][by][1]=true;
    int dis=0;
    while(!q.empty()){
        int n=q.size();
        while(n--){
            node u=q.front();q.pop();
            int x=u.x,y=u.y,op=u.flag;
            if(x==ex&&y==ey)
                return printf("%lld\n",dis),0;
            if(!op)
                for(int i=1;i<=2;++i){
                    int xx=x+dx1[i],yy=y+dy1[i];
                    if(xx>=1&&xx<=h&&yy>=1&&yy<=w&&s[xx][yy]!='#'&&!vis[xx][yy][1]){
                        vis[xx][yy][1]=true;
                        q.push({xx,yy,1});
                    }
                }
            else for(int i=1;i<=2;++i){
                    int xx=x+dx2[i],yy=y+dy2[i];
                    if(xx>=1&&xx<=h&&yy>=1&&yy<=w&&s[xx][yy]!='#'&&!vis[xx][yy][0]){
                        vis[xx][yy][0]=true;
                        q.push({xx,yy,0});
                    }
                }
        }
        ++dis;
    }
    printf("-1\n");
    return 0;
}