【多维BFS】ABC308 D

拼搏现实的明天。 2024-03-17 13:55 43阅读 0赞

**VP的时候居然花了半小时！**

**可恶！**

[D - Snuke Maze (atcoder.jp)][D - Snuke Maze _atcoder.jp]

题意：

![7999e0790fce4916868d4a3b9245e342.png][]

思路：

首先，我们发现到达一个格子之后，下一个格子的字符是确定的

**但是，下一个格子到底是哪个是不确定的**

**下一个格子不确定的时候就不能不多一维了**

决策是走到字符和预期相等的格子，因此预期字符会影响决策，因此需要把预期格子加入到状态中

至于预期状态怎么表示，因为是周期性的，可以模仿上次的，d=(d+1)%5即可

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=5e2+10;
    const int Inf=0x3f3f3f3f;
    
    struct ty{
        int x,y,d;
    };
    
    queue<ty> Q;
    
    int N,M;
    int dis[mxn][mxn][5],vis[mxn][mxn][5];
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
    string s[mxn],s2="snuke";
    
    bool check(int x,int y){
        return x>=1&&x<=N&&y>=1&&y<=M;
    }
    bool check2(int d,char x){
        return s2[d]==x;
    }
    void bfs(){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[1][1][1]=0;
        vis[1][1][1]=1;
        Q.push({1,1,1});
        while(!Q.empty()){
            ty u=Q.front();
            Q.pop();
            //cout<<u.x<<" "<<u.y<<'\n';
            for(int i=0;i<4;i++){
                int vx=u.x+dx[i];
                int vy=u.y+dy[i];
                if(check(vx,vy)&&check2(u.d,s[vx][vy])&&!vis[vx][vy][(u.d+1)%5]){
                    vis[vx][vy][(u.d+1)%5]=1;
                    dis[vx][vy][(u.d+1)%5]=dis[u.x][u.y][u.d]+1;
                    Q.push({vx,vy,(u.d+1)%5});
                }
            }
        }
    }
    void solve(){
        cin>>N>>M;
        for(int i=1;i<=N;i++){
            cin>>s[i];
            s[i]=" "+s[i];
        }
        bfs();
        if(dis[N][M][0]==Inf
        &&dis[N][M][1]==Inf
        &&dis[N][M][2]==Inf
        &&dis[N][M][3]==Inf
        &&dis[N][M][4]==Inf) cout<<"No"<<'\n';
        else cout<<"Yes"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[D - Snuke Maze _atcoder.jp]: https://atcoder.jp/contests/abc308/tasks/abc308_d
[7999e0790fce4916868d4a3b9245e342.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/fbf716474cf54f318979c3bf4c9bbb9b.png