Description
In a strange land far, far away, there is a house having N2 rooms numbered 1 to N2. The rooms are arranged randomly in an NxN grid. Each room has a locker in it. The locker in room number 1 is NOT locked, while all the lockers in all the other rooms are locked. The locker in room number 1 contains the key to the locker in room number 2, while the locker in room number 2 contains the key to the locker in room number 3 and so on. In general, the locker in room number K (K < N2) contains the key to locker in room number K+1. The locker in room number N2 contains a chest of gold and diamonds.
A thief, who wants to steal the chest, digs a tunnel and enters room number 1. From there onwards, he can proceed only to one of the adjacent rooms. Two rooms are considered adjacent only if they share a wall between them. It takes him 20 seconds to go from one room to the adjacent one, and negligible time to open the locker in it.
Find out the minimum time required to get to the chest.
Input Format
First line contains N
N lines follow
Each of these lines represent the arrangement of a row of rooms in the prison
Output Format
Time taken in the form
HH:MM:SS
Input Limits
1 <= N < 50
The minimum time taken is calculated as follows
00:00:00 The thief starts at Room 1 and has Key 2
00:00:20 Then he goes to Room 2 (adjacent)
00:00:20 He unlocks the locker and obtains Key 3(negligible time)
00:00:40 He goes to Room 1
00:01:00 He goes to Room 3
00:01:00 He unlocks the locker and obtains Key 4
00:01:20 He goes to Room 4 and gets the gold
