Time limit 2000/10000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Ibrahim Mesecan.
kht Puzzle
In 8-Puzzle, you are given a square frame
puzzle which consists of 8 numbered tiles
and one missing tile. By shifting the tiles
to the empty tile position, you are asked
to put the numbers in proper order. Your
professor is developing a program to solve
this problem automatically. For this, he
wants a program which solves kth puzzle problem
for k between 3 and 7. But solving big puzzles
takes too much time so he decided to limit
the search process. For that, he wants to search
at most 15 steps to decide when k is 3 or 4,
and at most 12 steps when 5 ≤ k ≤ 7.
Question:
Write a program that reads a matrix configuration.
And then, it finds if there is a solution within
the given steps length.
Input specification
In the first line, you will be given
an integer (n) where 3 ≤ n ≤ 7.
Then, in the following n lines you will be
given n integers where each number is
between 0 and n2-1
And, zero (0) represents the position of the
empty tile.
Output specification
If there is a solution show the number of minimum
steps. Show -1 (minus 1), if there is no solution
within the defined limits (max number of steps given).
Sample Input I
3
4 1 2
7 5 3
8 0 6
|
Sample Output I
7
|
Explanation
First, you move 8 to the position of 0,
then 7 and 4 are moved down, etc.
Для отправки решений необходимо выполнить вход.
|