HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN112 Homeworks 2013-2015 > problem:


15-SprHW-30. 50788 - Eight Puzzle

CEN112 Homeworks 2013-2015

Start: Dec.15.2013 at 12:00:00 PM
Finish: Dec.15.2013 at 05:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 14-Spr1-30. 50492 - Contest Score...
• 14-Spr1-40. 50538 - Sum of kth Dia...
• 14-Spr1-60. 50647 - Spiral
• 14-Spr2-20. 50442 - Polynomial Add...
• 14-Spr2-40. 50361 - Align Two Lists
• 14-Spr2-50. 50616 - Snake
• 14-Spr2-60. 50444 - n digit kth nu...
• 15-SprHW-20. 50446 - Snake
• 15-SprHW-30. 50788 - Eight Puz...
• 15-SprHW-40. 50746 - Most Visited
• 15-SprHW-60. 50516 - Lines
• 15-SprPr2-20. 50509 - Reading Book
• 15-SprPr2-60. 50766 - Word Puzzle
• 15-SprPr2-80. 50786 - Top Question
• 15-SprPrE1-20. 50785 - Swimming ...
• 15-SprPrE1-40. 50748 - Gold Store
• 15-SprPrE1-70. 50507 - Sequential ...

Feedback

If you notice incorrect translations in Contester, please let author know.

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



Для отправки решений необходимо выполнить вход.

www.contester.ru