1 人解决，2 人已尝试。
2 份提交通过，共有 11 份提交。
9.8 EMB 奖励。
1629. 迷宫
单点时限: 2.0 sec
内存限制: 256 MB
Tom 率领着一支探险队在沙漠中无意发现了一座古代文明留下的迷宫，为了抢在别的探险队到来之前了解迷宫中的奥秘，Tom 决定冒险走一次迷宫。
Tom 的队友在迷宫周围发现了一张地图，地图上记载：迷宫分为 n 行 m 列共 n*m 个方格，每个方格可能是空地或障碍物，迷宫的四周是墙；在其中一个空地中放置着一个开关和一本圣书，开关控制着迷宫中的 k 个魔鬼，圣书则是 Tom 想要的。迷宫中的魔鬼都是杀人不眨眼的猛兽，战胜他们的唯一办法就是关闭迷宫中的一个开关。迷宫只有一个入口，进出都只能经过这个入口。
一旦有人进入迷宫，迷宫会在 t 秒内自动毁灭，迷宫中一切都将消失（包括魔鬼和迷宫中的人）。Tom 想知道他能否在迷宫毁灭之前得到圣书、消灭魔鬼并安全离开。
第 i 个魔鬼第一时刻处在第 i1 行第 i2 列，面朝北。在某一时刻，如果魔鬼面前是障碍或墙，则它顺时针转 90 度；否则它将向前走一格。魔鬼向前走一格或转 90 度所需的时间均为 1 秒。
人在某一时刻可以向东西南北任一个空地走一格或原地不动，(人转身不需要时间)，耗时为 1 秒钟。若某一时刻人和一个魔鬼在同一个格子里，则人会被吃掉。当 Tom 走到有开关和圣书的格子里，如果格子里没有魔鬼，他就可以得到圣书并关闭所有魔鬼的开关，否则他将被吃掉。（注：当出现类似以下情况时，人不会被吃掉）
输入格式
第一行为 n，m，k，t，
以后 n 行每行 m 个字符描述迷宫的结构，’#’ 为障碍物，’.’ 为空地，’K’ 表示有开关和圣书的格子（也是空地）。
紧跟着 k 行，每行有两个数，描述这个魔鬼初始时所在的行和列。初始时所有魔鬼面朝北。
最后一行有两个数，描述唯一的入口所在的行和列。
输出格式
仅有一个数，表示最少需要的时间。如果不能完成任务并及时离开，则输出 0。
数据范围：
样例
Input
4 4 1 100 ..#. .K.. .#.. .... 1 1 4 4
Output
12 (注意：1、拿到圣书后要尽快离开迷宫，否则前面的努力就白费了！
创建: 17 年，3 月前.
修改: 7 年，2 月前.
最后提交: 1 年，5 月前.
来源: N/A
题目标签