SPIKES - Spiky Mazes


Jarmtin is interested in cultures and the history behind them. Of course this interest has a reason: as he studies the choivans’ past he discovers the hidden entrances of mazes he knows contain valuable information.  However there is a catch: the mazes contain spiky traps! Jarmtin is quite the agile type, but there is a limit to everyone, thus he will only be able to avoid a number of traps. This motivates the question can he make it through the mazes?

Jarmtin is interested in cultures and the history behind them. Of course this interest has a reason: as he studies the choivans’ past he discovers the hidden entrances of mazes he knows contain valuable information.  However there is a catch: the mazes contain spiky traps! Jarmtin is quite the agile type, but there is a limit to everyone, thus he will only be able to avoid a number of traps. This motivates the question can he make it through the mazes?

 

Input

The first line of a test case contains three integers n, m and j. n (2<=n<=40) the number of rows, m (2<=n<=40) the width of each row and j (0<=j<=20) the number of times Jarmtin can avoid spikes. Then n lines containing m characters; The character ‘x’ will be used for the place of the treasure, ‘@’ for an entrance (which is also an exit), ‘#’ for walls, ‘.’ for a safe walking tile and ‘s’ for spikes. Note that you cannot walk into walls and the maze is completely surrounded by walls outside what you can see. There is always at least one entrance/exit and always an x where the treasure is.

 

Output

You should output “SUCCESS” if Jarmtin can make it in and out alive, and “IMPOSSIBLE” if there is no way you can make it out alive.


Sample Input / Output

Example 1:

Input:

3 3 2

#@#

#s#

#x#

 

Output:

SUCCESS

 

Example 2:

Input:

4 4 3

####

@.s#

##.#

#xs#

 

Output:

IMPOSSIBLE

 

3 3 2
#@#
#s#
#x#

 

 


hide comments
karan_batra: 2017-09-20 05:38:17

Weak test cases.

kspoj: 2017-07-29 18:29:12

This prob gave me some hope in backtracking :)

Last edit: 2017-07-29 18:38:37
singhsauravsk: 2017-05-23 06:38:24

@andrewfang_21
See last sentence of input paragraph.

andrewfang_21: 2017-03-26 12:42:02

This maze only contains one treasure or more?

vengatesh15: 2017-03-15 20:27:08

easy one AC in 1 go:-)

Xvamp999: 2016-12-27 14:51:48

Simple DFS :)

xalen: 2016-12-01 06:56:38

Nice backtracking :) AC

Sushovan Sen: 2016-10-21 08:42:47

@k_a_singh:
1. There is only ONE treasure.
2. No he cannot move diagonally.
3. Only ONE test case.

tungtd95: 2016-10-06 15:08:37

Last edit: 2016-10-17 08:53:24
k_a_singh: 2016-07-03 13:00:35

Hi all, anyone, could you please give answer some questions which is not clear to me from this problem:
1- Can be more than one x (treasure) and need to collect all of them before exit the maze?
2- Can move diagonally?
3- Maximum number of test cases and where we will accept the number of test case ?

Last edit: 2016-07-03 13:09:22

Added by:Laurens
Date:2013-08-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self created problem