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.


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

hide comments
2023-04-08 12:22:23 Jarek Czekalski
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.

What may be important is that in this particular problem the program is run on 3 different input files and the sum of the times on all files must be below 0.5s (as explained to me in private message). While launching a Java app and reading the data consumes about 0.2 s, this is not gonna work in any way.

If you need some additional tricky cases, consider also such examples. These were failing at my first attempt:

1 3 4
SDM
.DU
.DU
.#U

1 4 4
SD#M
.DU.
.DU.
..U.
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
2016-08-03 11:32:47
@hodobox With case:
3 3 2
S.M
C#.
D..
###
C.C
.CU
how to resolve?

Last edit: 2016-08-03 11:36:06
2016-07-29 16:35:42
Tough one, but I liked it :P
non-spoiler clarifications:
1) @parijat: going up/down isn't counted as a step.
2) Input includes ~1000 worst-case testcases (big r,c,w and many coins) in one file (so think about time complexity/constants)
3) There can be cases like
1 2 4
SD
.D
DU
.M
or
1 2 4
SD
.D
.D
.M
The first case is not possible for Mario, the second can be solved in 1 step.

Last edit: 2016-07-29 17:38:14
2015-06-18 23:18:13 parijat bhatt
going up or down are counted as a step?
2015-05-19 20:29:21 Petar Bosnjak
P. setter can you tell me is my algorithm bad or only implementation , I/O are too slow?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.