HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN - 372 Homework > problem:


2015-60. 50505 - kht Puzzle

CEN - 372 Homework

Start: Sep.16.2015 at 10:00:00 AM
Finish: May.16.2016 at 02:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 2015-10. 50517 - Confusion Matrix
• 2015-20. 50518 - Histogram Equaliz...
• 2015-30. 50519 - Image Filtering
• 2015-40. 50498 - K-Means
• 2015-50. 50659 - Covariance Matrix
• 2015-60. 50505 - kht Puzzle
• 50. 50796 - KNN

Feedback

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

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.



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

www.contester.ru