Attack Time

All submissions for this problem are available.
Thanks to you, the humans are now finally in a shape to retaliate along with the Three
Legged Defenders. The plans are all made and its going to be mankind’s biggest battle
for survival. Only one piece remains.
The alien spaceship (and their military stronghold), which is currently at the ground
between the library building and the Faculty block, has a force field around it which
prevents any physical attacks. The takedown of this spaceship is a must for victory as
it’ll weaken their forces.
Thanks to the great hacker Ksholeet Deeparsharna’s notes, the military ‘experts’ have
figured out that the force field can in fact be disabled from within the ship, for a short
duration of 2 seconds which will be enough for our forces to take out the ship.
The alien ship is also known to be a mazelike structure (like a matrix). We enter the ship
at location 0,0 and the control room is at N1, N1 where N is the number of rows and
columns in the matrix. There is a door between certain rooms.
A human, masqueraded as an alien is being sent to disable the force field. Given the
structure of the ship, you have to find the shortest route and tell the number of seconds
after which our savior will be in the control room, once our savior has entered the ship. It
takes him exactly 1 second to travel from one room to another. He can either move
down, right or diagonally down in 1 move, when seeing the spaceship from the roof
view.
Tell the exact number of seconds. Save the human race.
Input
The first line contains T, the number of test cases.
Each test case starts with an integer N on a line (matrix is NxN)
N lines follow for each test case, with N space separated integers on each line, depicting
the matrix. The person can move into a cell if it is 1, and cannot go into that cell if it is 0.
Output
For each test case, on a single line, print the number of seconds after which to attack, if
the human inside takes the shortest route.
If there’s no path to the control room possible, print 1 on a single line.
Constraints
Should contain all the constraints on the input data that you may have. Format it like:
 1 ≤ T ≤ 100
 1 ≤ N ≤ 10
Example
Input: 4 3 1 0 0 0 1 0 0 0 1 3 1 0 0 1 0 0 1 1 1 3 0 1 0 0 0 1 0 1 1 3 1 0 0 0 0 0 0 0 1 Output: 2 3 3 1
Explanation
In the first case, the human can take the diagonal path 0,0 > 1,1 > 2,2 and reach in 2
seconds.
In the second case, the human can go 0,0 > 1,0 > 2,1 > 2,2 and reach in 3 seconds.
Author:  inoi_admin 
Tags  inoi_admin 
Date Added:  31102014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 