【BFS搜索】迷宫与陷阱

爱被打了一巴掌 2024-03-25 22:49 55阅读 0赞

**6，这道题我完全不会**

**完全没想到要开三维数组**

**感觉已经要寄了捏**

[迷宫与陷阱 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn]

![e4f7593b6ec37bbcd4b3a0a7f44a4545.png][]

思路：

因为遇到X是通过还是不通过取决于你的无敌值，因此我们需要多开一个维度记录无敌值（影响决策的因素作为一维）

然后判断就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e2+10;
    struct ty{
        int x,y,k,dep;
    };
    queue<ty> q;
    int n,k;
    string s[mxn];
    int vis[mxn][mxn][mxn];
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
    void bfs(){
        memset(vis,0,sizeof(vis));
        q.push({1,1,0,0});
        vis[1][1][0]=1;
        while(!q.empty()){
            ty u=q.front();
            q.pop();
            if(u.x==n&&u.y==n){
                cout<<u.dep<<'\n';
                return;
            }
            for(int i=0;i<4;i++){
                int vx=u.x+dx[i],vy=u.y+dy[i];
                if(vx<1||vx>n||vy<1||vy>n||s[vx][vy]=='#') continue;
                if(s[vx][vy]=='%'&&!vis[vx][vy][k]){
                    s[vx][vy]='.';
                    vis[vx][vy][k]=1;
                    q.push({vx,vy,k,u.dep+1});
                }
                if(s[vx][vy]=='X'&&u.k&&!vis[vx][vy][u.k-1]){
                    vis[vx][vy][u.k-1]=1;
                    q.push({vx,vy,u.k-1,u.dep+1});
                }
                if(s[vx][vy]=='.'&&!u.k&&!vis[vx][vy][0]){
                    vis[vx][vy][0]=1;
                    q.push({vx,vy,0,u.dep+1});
                }
                if(s[vx][vy]=='.'&&u.k&&!vis[vx][vy][u.k-1]){
                    vis[vx][vy][u.k-1]=1;
                    q.push({vx,vy,u.k-1,u.dep+1});
                }
            }
        }
    }
    void solve(){
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>s[i],s[i]=" "+s[i];
        bfs();
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/229/learning/?page=1&first_category_id=1&sort=students_count&name=%E8%BF%B7%E5%AE%AB%E4%B8%8E%E9%99%B7%E9%98%B1
[e4f7593b6ec37bbcd4b3a0a7f44a4545.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1d01a1afb1b546c9bc1891111c43f12c.png