当前位置：首页 > article >正文

[leetcode]864. 获取所有钥匙的最短路径(状态压缩bitmask+bfs)

article 2025/3/24 2:08:17

题目链接

题意

给定一个 $n\times m$ 的地图
‘.’ 代表一个空房间
‘#’ 代表一堵墙
‘@’ 是起点
小写字母代表钥匙
大写字母代表锁
钥匙和门互为大小写

目的是收集所有钥匙不一定要把门都打开
求最少需要几步
数据范围： $n,m\leq 30,k对钥匙和门,k\leq 6$

思路

数据很小显然搜索但是我一开始写的dfs错了求最少步数还是bfs更合适

本题的重点是vis有第三个状态就是当前手中的钥匙情况
而不是简单的标记走过的点不能再走因为可能需要走到一个角落拿钥匙还需要原路返回所以点可以重复走
但是如果拥有钥匙情况不变就不能重复走某个点因为这样是无意义的浪费步数

一定要想清楚这一维再开始写代码

Code

#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=40,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
char g[N][N];
int n,m;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool vis[N][N][1<<7];

class Solution {
public:
    int k=0;
    int sx,sy;
    int shortestPathAllKeys(vector<string>& grid) {
        n=grid.size(),m=grid[0].size();
        memset(vis,0,sizeof vis);

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                g[i+1][j+1]=grid[i][j];
            }
        }

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j]=='@') sx=i,sy=j;
                if(isupper(g[i][j])) k++;
            }
        }

        int ans=bfs();
        return ans;
    }

    int bfs(){
        queue<ar4>q;
        q.push({sx,sy,0,0});//steps keys
        vis[sx][sy][0]=1;

        int finalst=(1<<k)-1;
        

        while(q.size()){
            auto [x,y,steps,key]=q.front();q.pop();
            if(key==finalst){
                return steps;
            }

            for(int i=0;i<4;i++){
                int tx=x+dx[i],ty=y+dy[i];
                if(tx<1||tx>n||ty<1||ty>m||g[tx][ty]=='#') continue;
                if(vis[tx][ty][key]) continue;
                
                char c=g[tx][ty];
                int newkey=key;
                
                if(islower(c)){
                    newkey|=(1<<(c-'a'));
                }

                if(isupper(c)){
                    if((key&(1<<(c-'A')))==0) continue;
                }

                vis[tx][ty][newkey]=1;
                q.push({tx,ty,steps+1,newkey});
            }
        }
        return -1;
    }
};