E - GO!GO! サイコロ線路 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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 の範囲が異なっている。
あるデータセットに対して全て正しい解を出力すると、それ以外のデータセットで不正解を出力しても以下のように部分点が与えられる。
  • level1 (25 点) : N≦3
  • level2 (25 点) : N≦4
  • level3 (25 点) : N≦5
  • level4 (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