SMARIO - Super Mario Revisited
Mario is one the most famous video games ever. In this problem, we will be helping Mario save the princess (again :P). In this game of Mario, each world will be represented by a 2-D rectangular grid. There are multiple worlds and all the worlds are of size R x C. The world contains many objects each covering exactly one cell.
The cell with 'S' denotes Mario's starting position. A cell with '.' denotes an empty cell over which Mario can walk safely. From that cell he can move to any of its 4 adjacent cells (which share an edge with it). A cell with 'D' denotes a pipe that leads to the world below. A cell with 'U' denotes a pipe that leads to the world above. If Mario enters a cell containing a pipe, he must enter the pipe. A cell with 'C' represents a coin and Mario collects these. After collecting the coin, the cell becomes an empty cell. A cell with '#' denotes bricks and Mario can't enter this cell no matter what. A cell with 'M' denotes the monster (Bowser), Mario has to defeat Bowser to save the princess. Mario initially start from an empty cell.
Our Mario is very determined and so he will be always able to defeat Bowser on a 1 on 1 battle. But he is greedy and will always want to collect all the coins before going to save the princess. If he is not able to collect all the coins, he won't save the princess!. Help Mario to find the minimum number of steps to do this feat.
Note: If 'U' is present in top-most world or 'D' is present in the bottom-most world, Mario can't enter the cell.
Input:
Input contains multiple test cases (will never exceed 1000).
First line of each test case will have 3 integers R, C and W.
'R x C' represents Grid dimension and 'W' represents number of worlds.
It will be followed by R x W lines. Each line will have 'C' characters.
First R lines describe the first world, second R lines describe the second world and so on upto W worlds.
Input ends by the line '0 0 0'.
Output:
For each test case, print a single line “Mario saved the princess in K steps” where K is the minimum number of steps if he defeat the monster else print “Mario failed to save princess”.
Constraints:
1 <= R, C <= 15
1 <= W <= 10
0 <= [Total number of coins] <= 10
All characters in the grid will be from the set {'S', '.', 'M', 'C', 'D', 'U', '#'}
Sample
Input: 2 2 1 SM .D 2 2 2 SM .D C. UC 3 3 2 S.M C#. D.. ### C.C C.U 2 2 1 SM #C 0 0 0 Output: Mario saved the princess in 1 steps Mario saved the princess in 7 steps Mario saved the princess in 8 steps Mario failed to save princess
Explanation for third test case:
Mario is in (0, 0, 1) (first world), the optimal path is (0, 0, 1) → (1, 0, 1) → (2, 0, 1) → (2, 0, 2) → (1, 0, 2) → (1, 1, 2) → (1, 2, 2) → (2, 2, 2) → (2, 2, 1) → (1, 2, 1) → (1, 2, 0). So totally 10 steps which includes 1 Up and 1 Down. As there is no manpower required for Mario to take step in between the worlds omitting the 2 steps which gives us the answer 8.
hide comments
Jarek Czekalski:
2023-04-08 12:22:23
I was trying to solve this one in Java with no success. Even after thorough optimizations. So I rewrote it to c++. I got immediately accepted with time 0.34. On my computer Java solution is 2.5x slower, so no way to get it accepted. I couldn't even pass the first test set, which has only 31 cases.
|
|
code_ster:
2019-04-21 03:42:02
@hodobox can you please check my submission and point out what I am missing in my solution. submission id: 23664646 |
|
misawa:
2016-08-03 11:32:47
@hodobox With case:
|
|
hodobox:
2016-07-29 16:35:42
Tough one, but I liked it :P
|
|
parijat bhatt:
2015-06-18 23:18:13
going up or down are counted as a step? |
|
Petar Bosnjak:
2015-05-19 20:29:21
P. setter can you tell me is my algorithm bad or only implementation , I/O are too slow?
|
Added by: | Noob |
Date: | 2014-03-24 |
Time limit: | 0.300s-0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | Own Problem |