SMARIO  Super Mario Revisited
Statement
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 2D rectangular grid. There are multiple worlds and all the worlds are of size RxC. 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 topmost world or ‘D’ is present in the bottommost world, Mario can’t enter the cell.Input format:
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 format:
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’, ‘#’ }
INPUT:
2 2 1SM
.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
SAMPLE OUTPUT:
Mario saved the princess in 1 stepsMario saved the princess in 7steps
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 ommitting the 2 steps which gives us the answer 8.
hide comments
code_ster:
20190421 03:42:02
@hodobox can you please check my submission and point out what I am missing in my solution. submission id: 23664646 

misawa:
20160803 11:32:47
@hodobox With case:


hodobox:
20160729 16:35:42
Tough one, but I liked it :P


parijat bhatt:
20150618 23:18:13
going up or down are counted as a step? 

Petar Bosnjak:
20150519 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:  20140324 
Time limit:  0.300s0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  Own Problem 