2014《程序综合实验》实验指导书(3)(13)

实验指导书

当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：表示第j把钥匙存放在(Xi1,Yi1) 单元里，并且第j把钥匙是用来开启第Qi类门的。(其中1≤Qi≤P)

输出

对每组数据只输出一个整数T，表示麦克营救到大兵瑞恩的最短时间的值，若不存在可行的营救方案则输出-1。

样例输入

4 4 9 9 1 2 1 3 2 1 2 2 2 0 2 1 2 2 0 2 1 3 1 0 2 3 3 3 0 2 4 3 4 1 3 2 3 3 0 3 3 4 3 0 4 3 4 4 0 2 2 1 2 4 2 1

样例输出

14

三、实验方法

在不考虑有门和钥匙的时候，把相邻且没有墙的格子两两相连，权值为一，然后求最短路径就可以。

加入门的限制后，无法仅仅用最短路解决，所以将原图（用单独的数组存储格子之间的关系）复制2^p份，num[I,j,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]记录在拥有不同钥匙的情况下的节点编号，I记录行，j记录列，i1~i10取值范围为[0..1]，0表示没有该种钥匙，1表示有（多少把都可以），将有关系的节点之间连边，再整体做一遍SPFA就可以得到最优解。

有关系的节点：

1、相邻节点：中间没有墙和门或者有门但是两节点都在有该门钥匙的图上，则两节点间连一条权值为1的无向边。