GGAutomaton's Blog
0%

胜利大逃亡（great escape）

发表于 分类于 ，

【题目描述】

Ignatius 再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)…… 这次魔王汲取了上次的教训，把 Ignatius 关在一个 n*m 的地牢里，并在地牢的 某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始 Ignatius 被 关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius 每分钟只能从 一个坐标走到相邻四个坐标中的其中一个。魔王每 t 分钟回地牢视察一次，若发 现 Ignatius 不在原位置便把他拎回去。经过若干次的尝试，Ignatius 已画出整 个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前 走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口都算逃 亡失败。

【输入】

每组测试数据的第一行有三个整数 n,m,t(2<=n,m<=20,t>0)。接下来的 n 行 m列 为地牢的地图，其中包括:
. 代表路
* 代表墙
@ 代表 Ignatius 的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为 a-j
a-j 代表钥匙，对应的门分别为 A-J
每组测试数据之间有一个空行。

【输出】

针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开， 如果不能则输出-1。

【样例输入】

1
2
3
4
5
4 5 17
@A.B.
a*.*.
*..*^
c..b*

【样例输出】

16

【样例输入】

1
2
3
4
5
4 5 16
@A.B.
a*.*.
*..*^
c..b*

【样例输出】

-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
int n,m,t,sx,sy,ex,ey;
int door[25][25],key[25][25];
bool map[25][25],vis[25][25][1024];
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
struct node {
    int x,y,stat,time;
};
bool judgedoor(int x,int y,int stat) {
    if (door[x][y]==0) return true;
    if ((stat&(1 << door[x][y]-1))==0) return false;
    else return true;
}
bool judge(int x,int y,int stat) {
    if (judgedoor(x,y,stat) && !vis[x][y][stat]) return true;
    return false;
}
int bfs() {
    queue q;
    while (!q.empty()) q.pop();
    node now,next;
    now.x=sx;now.y=sy;
    now.time=0;now.stat=0;
    q.push(now);
    vis[sx][sy][0]=true;
    while (!q.empty()) {
        now=q.front();
        q.pop();
        if (now.time==t) return -1;
        if (now.x==ex && now.y==ey) return now.time;
        for (int i=0;i<4;i++) {
            next.x=now.x+dx[i];
            next.y=now.y+dy[i];
            next.time=now.time+1;
            next.stat=now.stat;
            if (next.x>=1 && next.x<=n && next.y>=1 && next.y<=m && map[next.x][next.y]) {
                if (key[next.x][next.y]!=0) {
                    next.stat=next.stat|(1 << key[next.x][next.y]-1);
                    vis[next.x][next.y][next.stat]=true;
                    q.push(next);
                }
                else if (judge(next.x,next.y,next.stat)) {
                    vis[next.x][next.y][next.stat]=true;
                    q.push(next);
                }
            }
        }
    }
    return -1;
}
int main() {
    while (scanf("%d%d%d",&n,&m,&t)!=EOF) {
        char ch;
        memset(map,0,sizeof(map));
        memset(door,0,sizeof(door));
        memset(key,0,sizeof(key));
        memset(vis,0,sizeof(vis));
        for (int i=1;i<=n;i++) {
            ch=getchar();
            for (int j=1;j<=m;j++) {
                ch=getchar();
                if (ch!='*') map[i][j]=true;
                if (ch=='@') sx=i,sy=j;
                if (ch=='^') ex=i,ey=j;
                if (ch>='A' && ch<='J') door[i][j]=ch-'A'+1;
                if (ch>='a' && ch<='j') key[i][j]=ch-'a'+1;
            }
        }
        int ans=bfs();
        printf("%d\n",ans);
    }
    return 0;
}