Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.
Eight Puzzle
In 8-Puzzle game, 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
to compare and calculate the distance of puzzles.
If two numbers are in the same x,y coordinates
then the distance is zero. If two numbers
are in different coordinates, manhattan distance
of two numbers is calculated.
Question:
Write a program that reads n matrix configuration
and then it finds the configuration with the
closest distance.
Input specification
You will be given two integers (n and k) where
0 ≤ n ≤ 500 and 1 ≤ k ≤ 10.
Then, in the following
n lines you will be given k2 integers
where each number is between 0 and k2
and zero (0) represents the position of the
empty tile.
Output specification
Show two numbers: Minimum distance and the
row of it. Note: If there are
several minimum results then show the first appearance.
Sample Input I
3 3
7 3 5 4 0 2 1 8 6
1 5 0 4 2 8 7 6 3
8 1 3 2 5 4 6 7 0
|
Sample Input II
3 4
4 13 14 2 10 8 5 3 6 1 12 9 11 15 7 0
8 12 10 3 4 7 2 14 9 6 15 5 0 13 1 11
1 3 15 5 14 2 10 12 0 7 9 8 11 6 4 13
|
Sample Output I
8 2
|
Sample Output II
32 3
|
Explanation
- The distance of the first row is 10
- The distance of the second row is 8
- The distance of the third row is 12
And so, the minimum distance is the second
row with 8 unit distance.
(For the sample 2)
When k = 4 it's called 15th puzzle:
4 13 14 2 10 8 5 3 6 1 12 9 11 15 7 0 distance = 36
8 12 10 3 4 7 2 14 9 6 15 5 0 13 1 11 distance = 37
1 3 15 5 14 2 10 12 0 7 9 8 11 6 4 13 distance = 32
Для отправки решений необходимо выполнить вход.
|