209006 - 孤岛营救

给定一个 N×M 的网格迷宫（N，M，P ≤ 10）。任意两个上下、左右相邻格子之间存在三种状态：互通、分类门、墙体。 1．互通：两格之间无遮挡，可以直接通行； 2．分类门：迷宫共有 P 类门，需要持有对应类型的钥匙方可通行； 3．墙体：完全不可通行。 迷宫中存在若干钥匙（S ≤ 14），每把钥匙对应一类门，放置在指定网格中。玩家走到对应格子可自动拾取钥匙，钥匙拾取后永久持有、无限次使用，重复经过该格子不会重复获取钥匙。 每次向相邻格子移动耗时 1 单位时间，拾取钥匙、开门均不消耗时间。 求从起点（1, 1）到达终点（N, M）的最短时间。若无法到达终点，输出 -1。

第一行三个整数 N、M、P，分别表示迷宫行数、列数、门的类别数。 第二行一个整数 K，表示迷宫中墙和门的总数量。 接下来 K 行，每行五个整数 X1、Y1、X2、Y2、G，保证两组坐标相邻： G = 0：两格之间为墙体，无法通行； G ≥ 1：两格之间为第 G 类门，需要对应钥匙通行。 接下来一行一个整数 S，表示迷宫中钥匙的总数。 接下来 S 行，每行三个整数 X、Y、Q，表示坐标（X, Y）的格子存放一把第 Q 类门的钥匙。

输出一个整数，表示从起点到终点的最短时间；若无法到达，输出 -1。