Design and implement an algorithm for finding the shortest path through a ``maze'' made from a two-dimensional array of weighted cells. Specifically, consider an N-by-N array of weighted cells, where one can travel from any cell to any vertically or horizontally (but not diagonally) adjacent cell. Your task is to find a path from the cell at row 1, column 1 to the cell at row N, column N for which the sum of the weights of all the cells on the path is minimized. Assume that the cell weights are random numbers between 0 and 1, but just use 10-bit precision.
For example, one might think of the array as a topographical map, and the cell weights as altitudes, so your path will tend to get to the goal by avoiding the mountains. If the weights were all 0 or 1, this also could encode a maze, so this is a generalization of maze traversal.
This is a relatively straightforward application of the ``priority-first'' search method described in class. Your task is to adapt that algorithm to this situation in a clean, efficient, and elegant manner.
Evaluate how fast your program is by seeing how large a maze it can solve in a fixed amount of time. Turn in your documented source code and runs that take 1 second, 2 seconds, and 10 seconds. Show the value of $N$, the number of cells that you touched in trying to compute the solution, and the total cell weight on the path computed.
Turn in a drawing of a solution for a 25-by-25 maze.
Due: 11:59PM Thursday, April 27.