Thornhill Computer Club 2024 - June Contest - Problem 4

An explorer has found himself deep in the jungle in Mexico, and needs to escape as fast as possible. However, because his companion, Wason, is a troll, the explorer needs to determine the amount of time to reach any of the exits, in case Wason rejects the others. The jungle is represented by a ~N~ by ~M~ grid, where the explorer can move up, right, down, and left.

Each cell of the grid is either a path (denoted by P), grove (denoted by G), hill (denoted by H), city (denoted by C), or river (denoted by R). The explorer takes 4, 8, 12, and 16 minutes respectively to move onto the cell. The explorer cannot move onto a river, which will always occupy the first row, last row, first column, and last column of the grid.

What are the shortest amounts of time for the explorer to move from its starting position, denoted by S, to the exits, denoted by .? It takes 1 minute to move onto either cell.

Input Specification

The first line of input contains two integers ~N~ and ~M~ ~(2 \le N, M \le 500)~, separated by spaces. The next ~N~ lines of input will contain ~M~ characters, each of which is one of 7 characters, P, G, H, C, R, S, or ..

There will be exactly one S character, and at least one . character.

Output Specification

For each exit, print one line with an integer, the minimum time for the explorer to move from the starting position to the exit. If it is not possible to reach the exit, output -1.

The output should be in row major order; the order of empty cells seen if the input is scanned line by line top-to-bottom and then left-to-right on each line. See the sample outputs for examples of row major order output.

Scoring

• Inputs 1-2: ~(N, M \le 4).~
• Inputs 3-9: No further constraints.

Sample Input 1

5 7
RRRRRRR
RH.P.HR
R.RCG.R
RRR.S.R
RRRRRRR

Sample Output 1

14
9
27
2
1
1

Explanation of Sample Output 1

To reach the top-leftmost cell, you move left, up, up, left, and left, and totaling the time results in 14 minutes.