Back

J. Freddy’s Maze Quest

Worth 8 point(s) - Runtime Limit: 3 seconds

Summary

Freddy the frog is about to enter a contest for solving a mazes that are especially designed for frogs. He will have to solve of up to 30 mazes, but some have no solution! He needs a genius who can write a program to help him.
A frog-maze is made up of an n×n rectangular grid. The cells of the grid are populated with non-negative integers, one per square. The goal is to jump along a legitimate path from the upper left corner to the lower right corner of the maze using the fewest jumps. The integer in a square dictates the distance the frog must jump away from that square. No jump is allowed that takes Freddy over the external wall of the maze.
All jumps must be either to the right or vertically downward. Note that a cell containing a 0 is a dead end which prevents any further progress.
Consider the 4 × 4 maze shown below:

_________________
| 2 | 3 | 3 | 1 |
_________________
| 1 | 2 | 1 | 3 |
_________________
| 1 | 2 | 3 | 1 |
_________________
| 3 | 1 | 1 | 0 |
_________________

Possible jump sequences are E2, S3, E1; S2, S1, E3; S2, E1, E2, S1, where E means east and S means south. The smallest number of jumps is 3.

Input

The input contains data for one to thirty mazes, followed by a final line containing only the integer ‘-1’. The data for a maze starts with a line containing a single positive integer n, 4 ≤ n ≤ 34, which is the number of rows in this maze. This is followed by n rows of data. Each row contains n single digits in [‘0’. . .‘9’], with no spaces between them.

4 
2331
1213 
1231
3110
4
3332
1213
1232
2120
5
11111
11111
11111
11111
11111
-1

Output

The output consists of one line for each maze, containing the problem number, starting at 1, then a space, and then the smallest number of jumps to get from the upper left corner to the lower right corner. If no path is possible, output the phrase “No Path”.

1 3
2 No Path
3 8