Problem Description
Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……
这次魔王汲取了上次的教训，把Ignatius关在一个n*m的地牢里，并在地牢的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试，Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。
Input
每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图，其中包括:
. 代表路
- 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙，对应的门分别为A-J
每组测试数据之间有一个空行。
Output
针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开，如果不能则输出-1。
Sample Input
4 5 17
@A.B.
a*..
…^
c…b
4 5 16
@A.B.
a*..
…^
c…b
Sample Output
16
-1
分析
记一道无聊的搜索
由于需要记录拿了哪些钥匙，于是记 f[i][j][k] 表示 到了点 (i.j)，钥匙的集合为 k 的最小步数，然后再加 spfa 即可通过。
坑点是第二次路过钥匙时可以不捡。
代码如下
#include <bits/stdc++.h>
#define inf 2147483647
using namespace std;
char mp[25][25];
int f[25][25][1 << 10], vis[25][25], V[25][25];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct node{
int x, y;
};
int main(){
int i, j, k, n, m, T, tx, ty, x, y, u, v, flag, ans;
node s, t;
while(scanf("%d%d%d", &n, &m, &T) != EOF){
ans = inf;
queue<node> q;
memset(f, 0, sizeof(f));
for(i = 1; i <= n; i++) scanf("%s", mp[i] + 1);
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
if(mp[i][j] == '@') s.x = i, s.y = j, q.push(s), f[i][j][0] = 1;
if(mp[i][j] == '^') tx = i, ty = j;
}
}
while(!q.empty()){
s = q.front(); q.pop();
x = s.x; y = s.y;
V[x][y]++;
vis[x][y] = 0;
//printf("%d %d====\n", x, y);
for(i = 0; i <= 3; i++){
u = x + dx[i];
v = y + dy[i];
flag = 0;
if(u >= 1 && u <= n && v >= 1 && v <= m){
//printf("%d %d=====\n", u, v);
if(mp[u][v] == '*') continue;
if(mp[u][v] == '.' || mp[u][v] == '^' || mp[u][v] == '@'){
for(k = 0; k < (1 << 10); k++){
if(f[x][y][k] && !f[u][v][k]) flag = 1, f[u][v][k] = f[x][y][k] + 1;
}
if(flag && !vis[u][v]) vis[u][v] = 1, t.x = u, t.y = v, q.push(t);
}
if(mp[u][v] >= 'a' && mp[u][v] <= 'j'){
j = mp[u][v] - 'a';
for(k = 0; k < (1 << 10); k++){
if(!((1 << j) & k)) continue;
if(f[x][y][k ^ (1 << j)] && !f[u][v][k]) f[u][v][k] = f[x][y][k ^ (1 << j)] + 1, flag = 1;
if(f[x][y][k] && !f[u][v][k]) flag = 1, f[u][v][k] = f[x][y][k] + 1;
}
if(flag && !vis[u][v]) vis[u][v] = 1, t.x = u, t.y = v, q.push(t);
}
if(mp[u][v] >= 'A' && mp[u][v] <= 'J'){
j = mp[u][v] - 'A';
for(k = 0; k < (1 << 10); k++){
if(!((1 << j) & k)) continue;
if(f[x][y][k] && !f[u][v][k]){
flag = 1, f[u][v][k] = f[x][y][k] + 1;
/*if(u == 6 && v == 1){
printf("%d %d\n", k, f[6][1][k]);
}*/
}
}
if(flag && !vis[u][v]) vis[u][v] = 1, t.x = u, t.y = v, q.push(t);
}
}
}
}
/*for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
printf("%d ", V[i][j]);
}
printf("\n");
}*/
//printf("===%d %d\n", tx, ty);
for(k = 0; k < (1 << 10); k++) if(f[tx][ty][k]) ans = min(ans, f[tx][ty][k]);
//printf("=======%d\n", ans);
if(ans - 1 >= T) printf("-1\n");
else printf("%d\n", ans - 1);
}
return 0;
}
京公网安备 11010502036488号