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?


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.


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:

3 3 2


Example 2:

4 4 3


hide comments
mahmudula2000: 2024-03-23 18:10:16

Very weak test case. I wrote 2 solutions, one correct another incorrect. Both of them got accepted.

yamamang: 2024-03-08 08:52:04

Maybe you can try this one:
3 4 1

yamamang: 2024-03-08 07:59:34

My algorithm can give the correct result for the use case given by the question, but the test result is WA.WHY!!!

maityamit: 2023-06-20 13:20:01

Yu,Yu... First time AC :)
Hints: Simple BFS Traversal

absidjdfhvdsb: 2022-09-13 19:58:36

@sakib_shahon notice @ is both start and exit point, so you have come back too at the start point

sakib_shahon: 2022-09-06 16:06:52

Can someone explain example 2 ? Why is it impossible ? I mean input 'j' has a value of 3? and only 2 spikes in the eaxample.

David: 2022-06-29 23:58:58

For @manish_kuri - the suggested problem does not match problem description. Problem states "always an x". The provided problem does not have an x (treasure location).

m_manas_s: 2021-09-09 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 weight-distance. Will bfs not completely miss the fact that a better path exists ?

Last edit: 2021-09-09 13:57:48
jdmoyle: 2021-07-12 22:17:28

@Laurens : this should be corrected: number of spikes from @ to x should be less than j/2 not j;
bfs works too.

Last edit: 2021-07-12 22:17:55
su1ts: 2020-01-26 14:10:04

Interesting problem(solved by bfs)
But think that test cases were weak

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