1629. 迷宫

Tom 率领着一支探险队在沙漠中无意发现了一座古代文明留下的迷宫，为了抢在别的探险队到来之前了解迷宫中的奥秘，Tom 决定冒险走一次迷宫。

Tom 的队友在迷宫周围发现了一张地图，地图上记载：迷宫分为 n 行 m 列共 n*m 个方格，每个方格可能是空地或障碍物，迷宫的四周是墙；在其中一个空地中放置着一个开关和一本圣书，开关控制着迷宫中的 k 个魔鬼，圣书则是 Tom 想要的。迷宫中的魔鬼都是杀人不眨眼的猛兽，战胜他们的唯一办法就是关闭迷宫中的一个开关。迷宫只有一个入口，进出都只能经过这个入口。

一旦有人进入迷宫，迷宫会在 t 秒内自动毁灭，迷宫中一切都将消失（包括魔鬼和迷宫中的人）。Tom 想知道他能否在迷宫毁灭之前得到圣书、消灭魔鬼并安全离开。

第 i 个魔鬼第一时刻处在第 i1 行第 i2 列，面朝北。在某一时刻，如果魔鬼面前是障碍或墙，则它顺时针转 90 度；否则它将向前走一格。魔鬼向前走一格或转 90 度所需的时间均为 1 秒。

人在某一时刻可以向东西南北任一个空地走一格或原地不动，(人转身不需要时间)，耗时为 1 秒钟。若某一时刻人和一个魔鬼在同一个格子里，则人会被吃掉。当 Tom 走到有开关和圣书的格子里，如果格子里没有魔鬼，他就可以得到圣书并关闭所有魔鬼的开关，否则他将被吃掉。（注：当出现类似以下情况时，人不会被吃掉）