Pro.ID1629 Title孤岛营救问题 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1629 AC2 Submit5 Ratio40.00% 时间&空间限制描述1944年,特种兵麦克接到国防部的命令,要求立即赶赴太平洋上的一个孤岛,营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里,迷宫地形复杂,但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形,其南北方向被划分为 n 行,东西方向被划分为 m 列, 于是整个迷宫被划分为 n×m 个单元。每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。南北或东西方向相邻的 2 个单元之间可能互通,也可能有一扇锁着的门,或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙,并且所有的门被分成 p 类,打开同一类的门的钥匙相同,不同类门的钥匙不同。 大兵瑞恩被关押在迷宫的东南角,即 (n,m) 单元里,并已经昏迷。迷宫只有一个入口, 在西北角。也就是说,麦克可以直接进入 (1,1) 单元。另外,麦克从一个单元移动到另一个 相邻单元的时间为 1,拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。 试设计一个算法,帮助麦克以最快的方式到达瑞恩所在单元,营救大兵瑞恩。 输入多测试用例。 第一行有三个整数,分别表示 n, m, p 的值。( n, m, p ≤ 10 ) 第二行是一个整数k,表示迷宫中门和墙的总数。( k < 150 ) 第 i+2 行 ( 1 ≤ i ≤ k ),有 5 个整数,依次为 xi1, yi1, xi2, yi2, gi :当 gi ≥ 1 时,表示 (xi1, yi1) 单元与 (xi2, yi2) 单元之间有一扇第 gi 类的门,当 gi = 0 时,表示 (xi1, yi1) 单元与 (xi2, yi2) 单元之间有一堵不可逾越的墙。 ( ∣ xi1 - xi2 ∣ + ∣ yi1 - yi2 ∣ = 1 , 0 ≤ gi ≤ p ) 第 k+3 行是一个整数 s,表示迷宫中存放的钥匙总数。 第 k+3+j 行 ( 1 ≤ j ≤ s ) ,有 3 个整数,依次为 xi1, yi1, qi,( 1 ≤ qi ≤ p ),表示第 j 把钥匙存放在 (xi1, yi1) 单元里,并且第 j 把钥匙是用来开启第 qi 类门。输入数据中同一行各相邻整数之间用一个空格分隔。 输出Description 1944年,特种兵麦克接到国防部的命令,要求立即赶赴太平洋上的一个孤岛,营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里,迷宫地形复杂,但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形,其南北方向被划分为 n 行,东西方向被划分为 m 列, 于是整个迷宫被划分为 n×m 个单元。每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。南北或东西方向相邻的 2 个单元之间可能互通,也可能有一扇锁着的门,或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙,并且所有的门被分成 p 类,打开同一类的门的钥匙相同,不同类门的钥匙不同。 大兵瑞恩被关押在迷宫的东南角,即 (n,m) 单元里,并已经昏迷。迷宫只有一个入口, 在西北角。也就是说,麦克可以直接进入 (1,1) 单元。另外,麦克从一个单元移动到另一个 相邻单元的时间为 1,拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。 试设计一个算法,帮助麦克以最快的方式到达瑞恩所在单元,营救大兵瑞恩。 Input 多测试用例。 第一行有三个整数,分别表示 n, m, p 的值。( n, m, p ≤ 10 ) 第二行是一个整数k,表示迷宫中门和墙的总数。( k < 150 ) 第 i+2 行 ( 1 ≤ i ≤ k ),有 5 个整数,依次为 xi1, yi1, xi2, yi2, gi :当 gi ≥ 1 时,表示 (xi1, yi1) 单元与 (xi2, yi2) 单元之间有一扇第 gi 类的门,当 gi = 0 时,表示 (xi1, yi1) 单元与 (xi2, yi2) 单元之间有一堵不可逾越的墙。 ( ∣ xi1 - xi2 ∣ + ∣ yi1 - yi2 ∣ = 1 , 0 ≤ gi ≤ p ) 第 k+3 行是一个整数 s,表示迷宫中存放的钥匙总数。 第 k+3+j 行 ( 1 ≤ j ≤ s ) ,有 3 个整数,依次为 xi1, yi1, qi,( 1 ≤ qi ≤ p ),表示第 j 把钥匙存放在 (xi1, yi1) 单元里,并且第 j 把钥匙是用来开启第 qi 类门。输入数据中同一行各相邻整数之间用一个空格分隔。 Output 每个测试用例输出一行:麦克营救到大兵瑞恩的最短时间。如果问题无解,则输出 −1。 Sample Input 4 4 9 Sample Output 14 Source 样例输入4 4 9 样例输出14 提示作者 |