Manha in the Shopping Mall
Time Limit: 3 sec
The Problem
Manha is a little intelligent girl. One day she went to a shopping mall to buy some cloths. Suddenly she wished to test ice-cream, so she decided to buy some clothes first from clothing shop and then to go ice-cream shop for ice-cream. This mall has several floors and have capsule lift that connects different floors. Manha’s current position, cloth shop position and the ice-cream shop could be in any floor.
Each movement made by Manha in x, y or z (moving to north, south, east, west, up or down a floor) counts like a step. Manha is a strategic little girl and she doesn’t want spend more steps than the necessary to reach clothing shop and then reach to ice-cream shop. Can you make a program that compute the minimum number of steps required to reach the clothing shop and ice-cream shop in the mall?
Every floor is described as a grid with the next conventions:
@ “#” Represents a wall.
@ “.” Represents a free square.
@ “^” Represents a capsule lift (Can go up or down to the next floor if and only if the next floor have an capsule lift in the same point). capsule lift could be used as a free squares too, meaning that Manha could pass through them without changing floor.
@ “*” Represents the current position of Manha. Could be in any floor.
@ “C” Represents a clothing shop. Could be in any floor.
@ “I” Represents a ice-cream shop. Could be in any floor.
Example:
Suppose in the mall have 3 floor 1st, 2nd and 3rd. Here the black squares denote walls, the white free squares and those marked with an “^” are capsule lift and “*” is the current position of Manha and “C” cloth shop and “I” ice-cream shop.
Here is the solution how Manha reach to the cloth shop. Note how from the first floor go to the third and then down again to the first, reaching the cloth shop possition in 13 steps.
As the same process she can goes to ice-cream shop from cloth shop in 1 step.
The Input
Input start with a integer number T which is test case (1 ≤ T ≤ 250). Each case starts with 3 integers L, W and H denoting respectively the number of rows and columns of each floor, followed by the number of floors (1 ≤ L,W,H ≤ 100). After that will be the description of each one of the H floors (Starting from the floor 1 and ending with the floor H). Each floor is conformed for W lines of L characters denoting the floor with the conventions given in the description. It is guaranteed that there will be one and only one character ‘C’ and one and only one character ‘I’ and one and only one character ‘*’ in the description of the the for each test case. For more clarification see the sample input format given below.
The Output
For each test case you have to print three lines. First line “Case x:” where x is test case number start from 1 to T. Second and third line described below:
If Manha can reach to the clothing shop from her current position and then can reach to the ice-cream shop from clothing shop
“Manha to C: N steps.”
“C to I: N steps.”
Here N is the minimum step number.
Or
If Manha can reach to the clothing shop from her current position and can not possible to reach the ice-cream shop from clothing shop
“Manha to C: N steps.”
“Not possible.”
Here N is the minimum step number.
Or
If Manha can not reach to the clothing shop from her current position but she can reach to the ice-cream shop from her current position
“Not possible.”
“Manha to I: N steps.”
Here N is the minimum step number.
Or
If Manha can not reach to the clothing shop neither reach to the ice-cream shop from her current position
“Not possible.”
“Not possible.”
Print a blank line after each test case. For more clarification see the sample output format given below.
Sample Input
2
4 4 3
*..^
#.##
..#^
^#CI
...^
.###
.#.^
^#..
.#.^
.#.#
.#.^
...#
2 4 2
.^#.
..#I
*^^C
####
Sample Output
Case 1:
Manha to C: 13 steps.
C to I: 1 steps.
Case 2:
Manha to C: 3 steps.
Not possible.
[University Level]
Inter School & College Programming Contest (ISCPC) 2017
Problem Setter: Shahin ShamS