O - 15 puzzle Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 6 点

問題文

4\times 4 のマス目について、次をみたす状態を 良い盤面 と定義します。

1 以上 15 以下の整数 i について i が書き込まれたマスがちょうど 1 つ存在する。
それら以外に何かが書かれたマスは存在せず、すなわち何も書かれていないマスがただ 1 つ存在する。

相異なる良い盤面 S, T が与えられます。
ここで、良い盤面 S は 16 個の整数 S_{i,j} (1\leq i,j\leq 4) によって与えられます。
1\leq S_{i,j}\leq 15 のとき、S の上から i 行目かつ左から j 列目のマスには S_{i,j} が書き込まれていることを、
S_{i,j}=-1 のとき、S の上から i 行目かつ左から j 列目のマスには何も書き込まれていないことを表します。
T も同様に 16 個の整数 T_{i,j} (1\leq i,j\leq 4) によって与えられます。

S から次の操作を繰り返して T の状態を作るために必要な最小の操作回数を出力してください。
ただし、30 回以下の操作で T の状態を作る事ができないとき（何回繰り返しても作る事ができない場合を含む）は -1 を出力してください。

  • 何も書き込まれていないマスと辺を共有するマスを 1 つ選び、そのマスに書き込まれている整数を何も書き込まれていないマスに書き込む。その後、選んだマスに書かれている整数を消す。

制約

  • -1\leq S_{i,j},T_{i,j}\leq 15
  • S_{i,j},T_{i,j}\neq 0
  • S,T は相異なる良い盤面である。
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

S_{1,1} S_{1,2} S_{1,3} S_{1,4}
S_{2,1} S_{2,2} S_{2,3} S_{2,4}
S_{3,1} S_{3,2} S_{3,3} S_{3,4}
S_{4,1} S_{4,2} S_{4,3} S_{4,4}
T_{1,1} T_{1,2} T_{1,3} T_{1,4}
T_{2,1} T_{2,2} T_{2,3} T_{2,4}
T_{3,1} T_{3,2} T_{3,3} T_{3,4}
T_{4,1} T_{4,2} T_{4,3} T_{4,4}

出力

S から問題文中の操作を繰り返して T の状態を作るために必要な操作回数を出力せよ。
ただし、30 回以下の操作で T の状態を作る事ができないときは -1 を出力せよ。

入力例 1

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 -1
1 2 3 4
5 6 -1 8
9 10 7 11
13 14 15 12

出力例 1

3

マス目の上から i 行目かつ j 列目のマスを (i,j) で表すことにします。
S における何も書かれていないマスは (4,4) です。
ここから次のようにして 3 回の操作で T を作る事ができます。

  • (3,4) を選ぶ。(4,4) に 12 を書き込み、(3,4) に書かれている整数を消す。
  • (3,3) を選ぶ。(3,4) に 11 を書き込み、(3,3) に書かれている整数を消す。
  • (2,3) を選ぶ。(3,3) に 7 を書き込み、(2,3) に書かれている整数を消す。

一方で、2 回以下の操作で T を作ることはできないため、3 を出力します。

入力例 2

-1 11 10 9
1 12 15 8
2 13 14 7
3 4 5 6
6 5 4 3
7 12 15 2
8 13 14 1
9 10 11 -1

出力例 2

-1

30 回以下の操作で T を作る事ができないため、-1 を出力します。

入力例 3

1 12 11 10
2 13 -1 9
3 14 15 8
4 5 6 7
1 10 5 14
2 11 6 15
3 12 7 -1
4 13 8 9

出力例 3

30

Score : 6 points

Problem Statement

A 4\times 4 grid is said to be good if it is in the following state:

For every integer i between 1 and 15, inclusive, there is exactly one cell with that integer written on it.
No other cell has something written on it. In other words, there is exactly one cell with nothing written on it.

You are given two distinct good grids S and T.
Here, the good grid S is given by 16 integers S_{i,j} (1\leq i,j\leq 4).
If 1\leq S_{i,j}\leq 15, it means that the cell in the i-th row from the top and j-th column from the left has S_{i,j} written on it;
if S_{i,j}=-1, it means that the cell in the i-th row from the top and j-th column from the left has nothing written on it.
Likewise, T is given by 16 integers T_{i,j} (1\leq i,j\leq 4).

Find the minimum number of times of performing the following operation to make the grid equal to T, starting from S.
If the grid cannot be made equal to T with 30 operations or less (including the case where any number of operations can do so), print -1 instead.

  • Choose a cell adjacent to the cell with nothing written on it, and write the integer written on the chosen cell to the empty cell. Then, erase the integer written on the chosen cell.

Constraints

  • -1\leq S_{i,j},T_{i,j}\leq 15
  • S_{i,j},T_{i,j}\neq 0
  • S and T are distinct good grids.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

S_{1,1} S_{1,2} S_{1,3} S_{1,4}
S_{2,1} S_{2,2} S_{2,3} S_{2,4}
S_{3,1} S_{3,2} S_{3,3} S_{3,4}
S_{4,1} S_{4,2} S_{4,3} S_{4,4}
T_{1,1} T_{1,2} T_{1,3} T_{1,4}
T_{2,1} T_{2,2} T_{2,3} T_{2,4}
T_{3,1} T_{3,2} T_{3,3} T_{3,4}
T_{4,1} T_{4,2} T_{4,3} T_{4,4}

Output

Print the minimum number of times of performing the operation in the problem statement to make the grid equal to T, starting from S.
If the grid cannot be make equal to T with 30 operations or less, print -1 instead.

Sample Input 1

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 -1
1 2 3 4
5 6 -1 8
9 10 7 11
13 14 15 12

Sample Output 1

3

We denote by (i,j) the cell in the i-th row from the top and j-th column from the left in the grid.
In S, the empty cell is (4,4).
One can perform three operations to obtain T.

  • Choose (3,4). Write 12 to (4,4), and erase the integer written on (3,4).
  • Choose (3,3). Write 11 to (3,4), and erase the integer written on (3,3).
  • Choose (2,3). Write 7 to (3,3), and erase the integer written on (2,3).

On the other hand, one cannot obtain T with two operations or less, so print 3.

Sample Input 2

-1 11 10 9
1 12 15 8
2 13 14 7
3 4 5 6
6 5 4 3
7 12 15 2
8 13 14 1
9 10 11 -1

Sample Output 2

-1

One cannot obtain T with 30 operations or less, so print -1.

Sample Input 3

1 12 11 10
2 13 -1 9
3 14 15 8
4 5 6 7
1 10 5 14
2 11 6 15
3 12 7 -1
4 13 8 9

Sample Output 3

30