Problem D
The Treasure Hunt
Input : treasure.in
Output : standard output
In this problem you will be given a map of a rectangular maze with square blocks. From each block you can move in four directions (N, E, W, S) and you lose some energy for every walk from one block to an adjacent one. Some blocks of the maze are really blocked - that is you cannot move to those blocks. Some other blocks contain some treasures that you will have to collect. Each treasure has a particular pickup cost and carrying cost associated with it. The pickup cost is the energy required to pick up the treasure from the floor and the carrying cost is the energy required to carry the treasure from one block to an adjacent one.
Now given a starting and ending location in the maze you will have to plan a single walk from the starting location to collect and carry all the treasures to the ending location at the expense of minimum energy.
Input
The first line of the input contains two integers R and C (each <= 20) describing the dimensions of the maze. Then follows R lines of C characters each representing the map of the maze. Each character corresponds to a square block and represents its property ('.' : an empty block, '#' : a blocked block, '*' : a block containing a treasure, 'S' : the starting block, 'T' : the ending block).
The next line contains an integer representing the energy required in calories for a walk from a block to an adjacent one.
The next line contains pairs of integers (Pi, Ci) representing the pickup and carrying cost in calories for the treasures given in the map from top to bottom and for the same row from left to right. There will be at most 10 treasures in the maze.
The input may contain multiple test cases and ends with two zeros for R and C.
Output
For each test case first output the hunt number. In the next line print the minimum energy required for the hunt. The third line will contain the description of the hunt as a sequence of characters containing 'N', 'E', 'W', 'S' and 'P'. 'N', 'E', 'W' and 'S' represent a walk to the north, east, west and south respectively and 'P' means that the treasure is picked up from the current location. If the hunt is impossible just output the sentence 'The hunt is impossible.' in a line by itself. Each test case output must be followed by a blank line.
Sample Input
5 8Sample Output
Hunt #1