Problem
Description
Bear is a bit older now, and so she needs lots of walking to burn off all that husky energy. The campus is probably one of the best places to walk a dog, considering all the paths, trees, people, and of course, THE SQUIRRELS! Unable to control the wild beast within her, Bear just loves to chase some squirrels and pounce on them. Unfortunately, this is quite a pain for the person holding the leash.
Given a grid representing campus, where each square contains the number of squirrels present, you are to find a path from the northwest corner to the southeast corner while minimizing the number of squirrels Bear encounters during her walk. Since we don't want to walk forever, we only move east, south, or south-east from one square to another until we reach the final location. Knowing what parts of campus to avoid due to the large amount of squirrels will help us greatly, so not only report the minimum number of squirrels we'd encounter, but also the actual path to take.
Input
You will be given a series of NxN grids where each square contains the population of the squirrels. The first line will contain the number of squares in each direction N, followed by the NxN grid itself. You may assume N is no bigger than 100. The end of input will be denoted by a 0 as the value of N. Here is a sample input:
5 1 5 2 3 6 4 3 2 1 2 3 8 4 2 1 0 5 2 3 4 3 1 4 2 1 0
Output
For each grid, output the minimum number of squirrels encountered on one line, followed by the path taken on the next (indicate paths by printing the sequence of squares visited as denoated by the squirrel population). In constructing path, favor horizontal movements first, then vertical, and finally diagonal as this will maximize the number of regions visited and give consistent path results. Here is a sample output:
12 1 3 2 2 3 1
Solution
Approach
Use dynamic programming to build a table where each square corresponds to a location in the grid. Each square should compute the minimum path from that square to all possible neighbors (north, west, northwest), and record which link was selected. The path can be recreated by starting from the bottom right square and following the links up towards the top left.
Input/Output
- Final Input: problem015.input
- Final Output: problem015.output