Challenge 16: Path Finding

In addition to playing board games with his children, the instructor is also slowly introducing video games to his kids¹. Because the kids can't type ² nor can they really use the mouse yet³, they can only play games such as Curious George - Pumpkin Boo!, which have limited player controls. In these sort of games, the player can move around the game space in the four cardinal directions (up, down, left, and right).

In some slightly more sophisticated games, tiles on the game map may have varying costs. This is usually done to simulate different types of terrain. For instance, crossing a tile that consists of grass will be cheaper than crossing a tile that consists of a mountain range.

To help the children navigate game maps that consist of tiles with varying weights, you are to implement Dijkstra's Shortest Path algorithm and compute the shortest path between two points on a tiled game board.

For instance, in the image to the right, the game board consists of six different types of tiles:

• : The forest tile has an f symbol and costs 3 units to traverse.

• : The grass tile has a g symbol and costs 1 unit to traverse.

• : The high-gross tile has a G symbol and costs 2 units to traverse.

• : The hills tile has an h symbol and costs 4 units to traverse.

• : The mountains tile has an m symbol and costs 7 units to traverse.

• : The river tile has a r symbol and costs 5 units to traverse.

The cost of each tile defines how much it costs to leave the tile. For instance, the "runner" in the image above is starting on a hill tile. Leaving this tile to move to any of its neighbors would cost 4 as specified in the table above.

Given this type of tiled board and the starting and ending position of a "runner", you are to determine the shortest path through the various tiles from the starting location to the end.

Input

You will be given a series of test cases in the following format:

TILES_N
TILE_NAME_0 TILE_COST_0
...
TILE_NAME_N-1   TILE_COST_N-1

MAP_ROWS MAP_COLUMNS
TILE_0_0    ...
...

RUNNER_START_ROW RUNNER_START_COL
RUNNER_END_ROW   RUNNER_END_COL

The first TILES_N indicates the number of different tiles. This is followed by the specified number tiles, where each line has the tile name (a single letter) and then its corresponding cost (an integer).

Next, the number of rows and columns in the map is given in MAP_ROWS and MAP_COLUMNS. This is followed by all the tile symbols where each row is separated by a newline and each column is separated by a space.

Finally, you are given the runner's starting and ending map coordinates.

You are to read and process test cases until you reach the end-of-file.

Example Input

For example, the test case corresponding to the image above would be as follows:

6
f 3
g 1
G 2
h 4
m 7
r 5
10 10
h f m r h g h f m r
m g h m h h G g G m
m r g f m G r m r G
f f r G G g h m f r
g r h r h G m f G h
m G G G r r g r f G
m g r m g G m h g f
G r f r m h m m m m
r m f G G g f g G h
h h h r m f f m h m
0 0
9 9

In this example, we would want to compute the path from the top-left corner to the bottom-right corner.

Output

For each test case, you are to compute the shortest path from the runner's starting position to the runner's ending position and output both the total cost of this path and the path itself in the following format:

Cost
ROW_0  COL_0
...

Example Output

For the example above, we would output the following

45
0 0
0 1
1 1
1 2
2 2
2 3
3 3
3 4
3 5
4 5
5 5
6 5
7 5
8 5
8 6
8 7
8 8
9 8
9 9

Note: In computing the total cost, remember to only include the cost of leaving a tile. This means, we should include the cost of leaving the starting tile but not out of the destination (because we never leave it).

Submission

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

$ cd path/to/cse-30872-fa17-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 challenge16               # Create and checkout challenge16 branch

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

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

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

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

$ .scripts/submit.py
Submitting challenge16 assignment ...
Submitting challenge16 code ...
  Result Success
   Score 6.00

$ curl -F source=@challenge16/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa17/challenge16
{"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 08 TA List to determine your corresponding TA for the merge request.