2150. 完美的拯救

单点时限: 2.0 sec

内存限制: 256 MB

一只可怜的蚂蚁被万恶的魔术师困在了一个魔方上,蚁后决定委派你去拯救这只可怜的蚂蚁,你被空投在魔方上的某个位置,你需要在最短的时间内找到那只蚂蚁,之后使用逃离卷轴返回蚁巢,你只能在格子线上行走,并且知道被困蚂蚁的位置,你需要出色的计算来完成这项艰巨的任务。
假设魔方是 3x3x3 个正方体小块组成,如下图所示

每面皆有 4x4 个格子道路可以行走。偶尔有些岔路点上有魔术师的魔兵把守,你不可以经过该岔路。现在以某个顶点为坐标原点建立空间坐标系,各个顶点坐标如上图所示。 eg. 你被空投至 (1,0,1), 你要去 (3,1,2), 并且 (2,1,3) 和 (3,1,1) 不可经过 : 那么你可选择如下的四步路线 :

(1,0,1) -> (1,0,2) -> (2,0,2) -> (3,0,2) -> (3,1,2),(也有别的选择)

输入格式

第一行有一个正整数 N (1<=N<=500), 表示测试数据的组数。

对于每组测试数据:

第一行有 7 个整数 : D, x1 y1 z1 x2 y2 z2, 分别是魔方的大小,你的当前坐标以及蚂蚁的坐标 (也为出口坐标);(两点均在魔方表面上).

第二行有 1 个整数 t, 表示不可经过的岔路个数。接下来 t 行,每行有一个坐标,是不可经过的岔路的坐标。
( 3 <= D <= 10, 0<=t<=10)

输出格式

对于每组测试数据输出一个数,即最小步数,若不可到达则输出-1

样例

Input
2
3 1 0 1 3 1 2
2
2 1 3
3 1 1
4 0 1 1 1 4 1
0
Output
4
4
Hint:
因为魔方是实体的,所以你只能在魔方的表面上行走.

15 人解决,38 人已尝试。

19 份提交通过,共有 118 份提交。

6.8 EMB 奖励。

创建: 14 年,7 月前.

修改: 5 年,5 月前.

最后提交: 10 月,3 周前.

来源: 第一届程序设计竞赛

题目标签