50004. 15 - puzzle

I'm a slow walker, but I never walk backwards.

Problem description

15-Puzzle is a game of moving 15 numbers in a 4 by 4 grid. There are 15 numbers from 1 to 15, each in a grid cell, and the only remaining cell is empty. One can move the number adjacent to the empty cell into it. This will exchange the positions of the empty cell and the number you just moved. Please refer to the following figure. For ease of illustration we use 0 to indicate the empty cell.

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

By moving the 15 to the left, we have the following configuration. If the configure is exactly like this, then we will stop. This is called a "winning configuration" .

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

You need to write a program to simulate the moving process. You will be given the initial configuration, and a sequence of n moves. A move is a number that was moved in a time step. For example, in the previous example the move is 15. A move could be invalid if it is a number not adjacent to the empty cell, or it is not between 1 and 15. In the previous example the only valid moves are 11, 14, and 15.

Your task is to output the final configuration after applying all the moves. Note that if you encounter an invalid move you should ignore that invalid move. Also note that if you get into the winning configuration, you should report the move that cause the winning configuration, and stop immediately.

Subtasks

  • 10pt. $n$ is $0$, and the input is not a winning configuration.
  • 50pt. $n$ is between $1$ and $100$, All moves are valid, and the moves will not get into a winning configuration.
  • 20pt. $n$ is between $1$ and $100$, All moves are valid, and the moves could get into a winning configuration.
  • 20pt. $n$ is between $1$ and $100$, the moves could be invalid, and the moves could get into a winning configuration.

Input Format

There are 5 rows in the input. The first 4 rows are the puzzle. There are 4 numbers in each rows. The last row is the move sequence. Each number means that that number in the puzzle has to move to the 0's position. The move sequence is end by 0.

Output Format

There are 5 rows in the output. The first 4 rows are the final result of the puzzle. The last row is the result. If the puzzle will not get into a winning configuration, the output will be 0. If the puzzle will get into a winning configuration, the output will be 1 and the last step.

Sample Input 1

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

Sample Output 1

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

Sample Input 2

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

Sample Output 2

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

Discussion