In this assignment, our goal is to develop a program for solving an input number maze. The assignment is adapted from Exercise 11 of Chapter 5 of our textbook. A number maze M[1..n, 1..n] is an n by n grid of non-negative integers. A token is initially placed in the upper left corner, on the square (1,1). We want to move it to the lower right corner, the square (n,n), using a minimum number of moves. If the token is on square (i,j), then in a single move, we can move it up, down, left, or right, by M[i,j] squares. (Of course, any such move is valid only if we stay within the grid.) Note that in this assignment we allow M[i,j] to be 0; if the token reaches such a square (i,j), it cannot move any further. See Exercise 11 of Chapter 5 of our textbook for an illustration.

Assume that the input number maze is specified in a file whose first line specifies n, the length of the grid. The next n*n likes specify the entries of the maze M row by row -- so the first n of these lines specify M[1,1..n], the next n lines specify M[2,1..n], and so on. Here is a file that shows the format in which the input data is given; here n = 5. Here is the same input data displayed as a maze.

Write a program that asks for an input file that contains the input number maze M in the above format, and outputs the minimum number of moves required to solve the maze; if the maze does not admit a solution, your program should output that. There is no need to output the actual sequence of moves. For full credit, your program should be able to correctly solve inputs of length n = 1000 reasonably fast, say within a second to two minutes. Your program should be sequential, that is, it should not resort to any kind of parallelism like threads, GPU, etc. We want to keep the focus on algorithmic ideas in the sequential setting. We will accept programs in Python, Java, C, and C++.

The homework is due Thursday, April 30, at 11:59 pm. It is worth 60 points.

Submission Instructions:

Please submit a document that (a) describes your algorithm and any data structures you use in your implementation; (b) the minimum number of moves and the running time in milliseconds on the test inputs with n = 100 and n = 1000 below; and (c) instructions for running your program. In addition, submit the program. All submissions are to be done on ICON.

Your algorithm description should be detailed enough that we should not have to read your code. When calculating running time, exclude the time for reading in the data from the input file.

Sample Inputs