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
hide comments
m_manas_s:
20210909 13:57:09
How to solve it using standard bfs? This seems like a weighted graph problem where I weighted edges connected to spikes as 1, rest 0. Then I used dijkstra to find the entrance from 'x' with least weightdistance. Will bfs not completely miss the fact that a better path exists ? Last edit: 20210909 13:57:48 

jdmoyle:
20210712 22:17:28
@Laurens : this should be corrected: number of spikes from @ to x should be less than j/2 not j;


su1ts:
20200126 14:10:04
Interesting problem(solved by bfs)


sandeepd:
20191126 18:35:47
Nice problem but weak test cases. Even partially correct solution passes. Last edit: 20191126 18:36:07 

ankit_btech:
20190718 22:45:52
Here is a hint to a different approach: Use Dijkstra's algorithm. 

loc_1103:
20190327 07:50:10
Poorly written.Real question is there a path from any @ to x such that number of spikes in that path is less than j/2


manish_kuri:
20190321 07:33:35
when you done this problem:


campabell:
20181120 14:00:10
I am getting runtime error (NZEC)...can anyone tell me how to rectify it?


maratha:
20180928 21:55:13
A must do problem for understanding backtracking in DFS. 

g_somani:
20180613 08:57:32
The problem is to find the entrance/exit which is at least spikedistance from the treasure. He will enter as well as exit from the same cell. 
Added by:  Laurens 
Date:  20130810 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Self created problem 