← 返回题目列表

AtCoder · tenka1_2012_final_e

E. 走!走!骰子轨迹

中文机器翻译题面 查看原题

問題文

N × N 一个骰子被 XY 安排在平面上,如下图所示。
可以移动到相邻面数字相同的骰子上,您想要从左上角的骰子移动到右下角的骰子。
骰子 90° 给定它可以旋转的次数,打印它必须经过的最小骰子数。
另外,如果您无法从左上角移动到右下角 打印 -1 。
一旦你开始移动,你就不能再掷骰子了。

入力

输入是按以下格式从标准输入给出的。
N M
c_{00Z}c_{00X} c_{01Z}c_{01X} c_{02Z}c_{02X} … c_{0(N-1)Z}c_{0(N-1)X}
c_{10Z}c_{10X} c_{11Z}c_{11X} c_{12Z}c_{12X} … c_{1(N-1)Z}c_{1(N-1)X}
:
:
c_{(N-1)0Z}c_{(N-1)0X} c_{(N-1)1Z}c_{(N-1)1X} c_{(N-1)2Z}c_{(N-1)2X} … c_{(N-1)(N-1)Z}c_{(N-1)(N-1)X}
  • 输入是 N+1 。
  • 1 骰子的垂直和水平长度显示在行中。 N\ (1≦N≦6) 以及您可以掷骰子的次数。 M\ (0≦M≦1,000) 。 表示
  • 2 从行 N+1 到第…行 N 行显示骰子信息, 直到1 减去 6 的整数 2 每个数字之间以半角空格分隔。
  • 骰子信息是 如下所示,使用 2 整数 i\ (0≦i≦N-1)、j\ (0≦j≦N-1)。
    1. c_{ijZ} … Z 面向轴正方向,坐标 (x_i,y_j) 处骰子的价值
    2. c_{ijX} … X 面向轴正方向,坐标 (x_i,y_j) 处骰子的价值
  • M 是模具可以旋转的次数,模具的旋转定义如下。
    1. Z 反对 90° 旋转 计为 1 次。
    2. X 反对 90° 旋转 计为 1 次。
    3. Y 反对 90° 旋转 计为 1 次。
    4. 也就是说,骰子的旋转轴是 3 有两个。

部分点

测试数据如下所示。 包含 4 类型的数据集之一,每个数据集代表一叠骰子的长度和宽度。 N 范围不同。
如果某个数据集输出所有正确答案,则即使其他数据集输出错误答案,也会如下所示给出部分分数。
  • 1级(25分): N≦3
  • 2级(25分): N≦4
  • 3级(25分): N≦5
  • 4级(25分): N≦6

出力

骰子 来自 c_{00} 的骰子 移动到 c_{(N-1)(N-1)} 时必须通过的最小骰子数量。 如果
骰子 来自 c_{00} 的骰子 移动到 c_{(N-1)(N-1)} 无法访问,-1 。
请注意,输出末尾需要换行。

補足

本题所用骰子的展开图和组装版本如下所示。 如果用

入力例 1

3 1
24 35 32
13 15 23
32 45 62

出力例 1

5
  • 入力例 1 来表示,就会像上图一样。
  • 座標 (0,1) 骰子(箭头所指的骰子) Y 负方向轴 90° 旋转时,它看起来像上图一样。
  • 此时左上方的骰子 c_{00} 到右下骰子 至 c_{22} 屁 5 通过两个骰子即可到达。

入力例 2

4 2
51 63 26 51
64 21 13 14
51 56 35 62
41 14 21 31

出力例 2

-1

入力例 3

4 3
51 63 26 51
64 21 13 14
51 56 35 62
41 14 21 31

出力例 3

9