You were supposed to have a test today in your CS class, but your CS teacher was out sick and your substitute Mr. Monroe seems a little weird. As he hands out the tests, you read the first problem:
The maze will consist of grid locations marked as either empty (.) or containing a wall (#). You may travel either up, down, left or right, but not diagonally. For each maze, you may travel through a specified maximum number of walls from the start square (S) to the finish square (E), though you need not travel through exactly that number. Your want to find the shortest path through the maze, where path length is calculated as follows: empty squares incur a distance penalty of 1 and walls incur a distance penalty of 3. The start square is not counted (consider it to be location 0), but the end square is. So a path that looks like S#..E will have a path length of 6.
- You are being chased through a maze by a group of hungry velociraptors! As you survey your apparently hopeless condition, you notice that the walls of the maze are low enough to climb over, but that climbing is substantially slower than fleeing on foot. If you spend too much time climbing, the velociraptors will surely catch you. Your only hope of survival is finding the shortest path through to the maze exit, where your velociraptor-proofed fortress awaits. Remember, raptors run at 10 m/s and they do not know fear.
The maze will consist of grid locations marked as either empty (.) or containing a wall (#). You may travel either up, down, left or right, but not diagonally. For each maze, you may travel through a specified maximum number of walls from the start square (S) to the finish square (E), though you need not travel through exactly that number. Your want to find the shortest path through the maze, where path length is calculated as follows: empty squares incur a distance penalty of 1 and walls incur a distance penalty of 3. The start square is not counted (consider it to be location 0), but the end square is. So a path that looks like S#..E will have a path length of 6.
Input Format
Line 1: three space-separated integers r c w, indicating the number of rows, the number of columns, and the maximum number of walls allowed, respectively Lines 2 ≤ i ≤ r + 1: a string of c characters that denotes row i - 1
Sample Input
5 5 2
S....
##.##
..#.E
.####
.....
Output Format Line 1: an integer p, either the minimum path distance from start to finish, or -1 if no valid path exists
Sample Output
8
You must be logged in to submit a solution.