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 2-D 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 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

SAMPLE OUTPUT:

Mario saved the princess in 1 steps

Mario 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: 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:
3 3 2
S.M
C#.
D..
###
C.C
.CU
how to resolve?

Last edit: 2016-08-03 11:36:06
hodobox: 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
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