品牌建设成效_企业网站欣赏郑州企业形象设计_如何进行新产品的推广_新闻最近的大事10件

题目链接

题意

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

目的是收集所有钥匙 不一定要把门都打开
求最少需要几步
数据范围：$$n,m\le 30,k对钥匙和门,k\le 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 keysvis[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;}
};

实现细节

如何使用bitmask状态压缩 来表示当前钥匙状态？

在二进制意义上看 最多6个钥匙 也就是最多$(1<<6{)}_{10}=2^6=64$
$vis中30\ast 30\ast 64空间完全开得下$

说回bitmask 二进制上每一位代表这一位所对应的钥匙是否获得 通过c-'a’进行映射

队列存储四维内容

保存这个状态的坐标 走的步数 当前钥匙状态