一共有10把钥匙，用10位的二进制反映钥匙的拥有情况
#include <iostream> #include <cstring> #include<cstdio> #include <queue> using namespace std; char maze[21][21]; int n,m,t; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int vis[1024][21][21]; //2^10-1 = 1023 typedef struct node{ int x,y,key,step; }Node; queue<Node> q; int bfs(int sx,int sy){ while (!q.empty()) q.pop(); vis[0][sx][sy]=1; Node s={sx,sy,0,0}; q.push(s); while(!q.empty()){ Node u = q.front(); q.pop(); int x,y,key,step,nx,ny,nkey,nstep,d; x=u.x; y=u.y; key=u.key; step=u.step; if(step >= t-1) return -1; for(d = 0;d < 4;d ++){ nx=x+dx[d]; ny=y+dy[d]; nkey=key; if (!maze[nx][ny] || maze[nx][ny]=='*') continue; if (isupper(maze[nx][ny])) { int t=maze[nx][ny]-'A'; if (!(key&(1<<t))) continue; //钥匙不匹配 } if (islower(maze[nx][ny])) { int t=maze[nx][ny]-'a'; nkey=key|(1<<t); //更新钥匙状态 } if (vis[nkey][nx][ny]) continue; vis[nkey][nx][ny]=1; nstep=step+1; node v={nx,ny,nkey,nstep}; if (maze[v.x][v.y]=='^') return v.step; q.push(v); } } return -1; } int main() { int x,y,ans,i,j; while(cin >> n >> m >> t){ memset(vis,0,sizeof(vis)); for (i=1;i<=n;i++) scanf("%s",maze[i]+1); for (i=1;i<=n;i++) for (j=1;j<=m;j++) if (maze[i][j]=='@') { x=i; y=j; maze[i][j]='.'; } ans = bfs(x,y); cout << ans << endl; for (i=0;i<=n+1;i++){ for (j=0;j<=m+2;j++){ cout << maze[i][j] << " "; } cout << endl;} } return 0; }