本文最后更新于14 天前，其中的信息可能已经过时，如有错误请发送邮件到big_fw@foxmail.com
最近想写迷宫了，迷宫好玩
HDU 1429：胜利大逃亡(续)
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 65536/32768 K (Java/Others)
题目描述
Ignatius 再次被魔王抓走了。这次魔王汲取了上次的教训，把 Ignatius 关在一个 n * m 的地牢里，并在地牢的某些地方安装了带锁的门，而开门的钥匙藏在地牢的其他位置。
- 刚开始，Ignatius 被关在
(sx, sy)的位置。 - 离开地牢的出口在
(ex, ey)的位置。 - Ignatius 每分钟只能从当前坐标移动到相邻的四个坐标之一。
- 魔王每
t分钟会回地牢视察一次，若发现 Ignatius 不在原位置，便会把他拎回去。
经过若干次尝试，Ignatius 已经画出了整个地牢的地图。现在请你帮他计算能否再次成功逃亡。
逃亡成功判定： 只要在魔王下次视察之前走到出口就算离开地牢。如果魔王回来的时候刚好走到出口，或者还未到出口，均算作逃亡失败。
地图元素说明
地图由以下字符构成：
.：代表通路*：代表墙壁（不可通行）@：代表 Ignatius 的起始位置^：代表地牢的出口A-J：代表带锁的门（对应的钥匙分别为a-j）a-j：代表钥匙（对应的门分别为A-J）
输入格式
包含多组测试数据。每组测试数据之间有一个空行。
- 每组数据的第一行包含三个整数
n,m,t(2 <= n, m <= 20,t > 0)，分别代表地牢的行数、列数以及魔王视察的时间间隔。 - 接下来的
n行，每行包含m个字符，表示地牢的地图分布。
输出格式
针对每组测试数据：
- 如果可以成功逃亡，请输出最少需要多少分钟才能离开。
- 如果不能逃亡（无法到达出口或超时），则输出
-1。
样例输入
4 5 17
@A.B.
a*.*.
*..*^
c..b*
4 5 16
@A.B.
a*.*.
*..*^
c..b*
样例输出
16
-1
思路
状态压缩，因为一共10把钥匙，我们只能用状态压缩，一二维记录坐标，三维存有什么钥匙
理解，状态压缩是为了同时记录多个状态而产生的，状态是有（1），无（0）
代码
// Sunshine, sunshine, ladybugs awake!
// Clap your hooves and do a little shake!
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
using PII=pair<int,int> ;
const int mod=666623333;
const int MAXN=25;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool vis[MAXN][MAXN][2<<10];
char g[MAXN][MAXN];
int n,m,k;
struct Node{
int x,y,key,tim;
};
void solve() {
memset(vis,false,sizeof(vis));
int st_x,st_y,ed_x,ed_y;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
if(g[i][j]=='@'){
st_x=i;
st_y=j;
}
if(g[i][j]=='^'){
ed_x=i;
ed_y=j;
}
}
}
queue<Node> q;
q.push({st_x,st_y,0ll,0ll});
vis[st_x][st_y][0]=true;
while(!q.empty()){
auto [x,y,key,t]=q.front();
q.pop();
if(t>=k){
cout<<-1<<endl;
return ;
}
if(x==ed_x&&y==ed_y){
cout<<t<<endl;
return ;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(g[nx][ny]=='*')continue;
if(nx<1||nx>n||ny<1||ny>m)continue;
int nkey=key;
if(g[nx][ny]>='A'&&g[nx][ny]<='J'){
if(!(nkey&(1ll<<(g[nx][ny]-'A')))){
continue;
}
}
if(g[nx][ny]>='a'&&g[nx][ny]<='j'){
nkey|=(1ll<<(g[nx][ny]-'a'));
}
if(!vis[nx][ny][nkey]){
vis[nx][ny][nkey] = true;
q.push({nx, ny, nkey, t + 1});
}
}
}
cout << -1 << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin >> t;while (t--)
while(cin>>n>>m>>k) solve();
return 0;
}
