Challenge 11: Kakamora

Moana needs to take the heart of Te Fiti back to its original master. To do this, she must go on a perilous voyage and see how far she'll go. Unfortunately she doesn't know the way and there are a bunch of cute but deadly Kakamora in her path.

Given a grid representing the ocean, where each square contains the number of Kakamora present, you are to find a path from the northwest corner to the southeast corner while minimizing the number of Kakamora she encounters during her voyage.

Since Moana is in rush, she only moves east, south, or south-east from one square to another until she reaches the final location. Knowing what parts of the ocean to avoid due to the large amount of Kakamora will help her greatly, so not only report the minimum number of Kakamora she'd encounter, but also the actual path to take.

Do a good job and you can tell Moana: you're welcome.

Input

You will be given a series of NxN grids where each square contains the population of the Kakamora. 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 larger than 100. The end of input will be denoted by a 0 as the value of N.

Example 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 Kakamora encountered on one line, followed by the path taken on the next (indicate paths by printing the sequence of squares visited as denoted by the Kakamora population).

When re-constructing path backwards, favor horizontal movements first, then vertical, and finally diagonal as this will maximize the number of regions visited and give consistent path results.

Example Output

12
1 3 2 2 3 1

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa18-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge11               # Create and checkout challenge11 branch

$ $EDITOR challenge11/program.cpp           # Edit your code

$ git add challenge11/program.cpp           # Stage your changes
$ git commit -m "challenge11: done"         # Commit your changes

$ git push -u origin challenge11            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge11 assignment ...
Submitting challenge11 code ...
  Result Success
   Score 6.00
    Time 0.00

$ curl -F source=@challenge11/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa18/challenge11
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 06 TA List to determine your corresponding TA for the merge request.