ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Разделы > Поиск > задача:


50788 - Eight Puzzle

Гость
• Вопросы к жюри (1)

Задачи раздела

• 50483 - Group Total
• 50331 - Number of Numbers over A...
• Raporti Javor
• 50861 - The largest Student Group
• 50815 - Breaking the Bunker
• 50437 - Age Labeling
• 50500 - Find Student
• 50786 - Top Question
• 50788 - Eight Puzzle
• 50504 - School contest
• 50787 - Expected Value
• 50859 - Low performance
• 50785 - Swimming Contest
• 50826 - Olive Containers
• 50866 - Buy the cheapest
• 50999 - Overlapping Trips
• 50507 - Sequential Numbers

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
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