SPOJ.com - Problem ROT

ROT - Rescue On Time

no tags

In the future there is an agency that works on rescuing people from the “bad guys”, those guys are a super secret evil agency that is on a super secret bunker that everybody knows, especially the agency we mentioned before. This agency (the good one) has a very particular thing, they can do time travel either to the future or to the past and they can do it how many times they want, but only one minute to the future or one minute to the past, or even stay in the present, it is impossible to go for example three minutes to the future or two minutes to the past; our agency wants to rescue only one hostage since the “bad guys” are really dumb and they can kidnap only one person and keep it hidden (it is dumb because the bunker is huge), now here is the deal, the agency has contracted us to do a program that tells the minimum number of time steps the agent of our agency should make to save the hostage (I am so lazy that you will do it all by yourself). It is important to know that at some point after certain amount of time the hostage will be killed so we don´t want to go over that time, never! And also we don´t want to get back on a time where the hostage isn´t in the bunker yet so remember that!, he can take a step into any adjacent direction but not in diagonals, and it is no meaning into wait on a position because the agent can use time as he wants.

‘X’ represents the place where the agent starts, it is guaranteed that the agent starts at the time 1.
‘#’ represents a wall.
‘s’ represents a free space.
‘!’ represents a “bad guy”.
‘O’ represents our objective.

Input

The first line of input is T the number of test cases, there will be several test cases T <= 10. Next line of input contains C, R, Time, which are Columns <= 15, Rows <= 15 and of course the Time <= 10 (Right after that maximum time the hostage will be killed and before time 1 there will be no hostage to save so is useless to go there) Time is measured in minutes, after that, Time lines will follow with a matrix of RxC Representing the actual position of guards and new free spaces after time traveling (Obviously walls will not move, and neither does the hostage because he is tied up.)

Output

Just output the minimum number of time steps that takes to our agent to get to the hostage, if it is impossible to get to the Hostage then should output: “Hostage is death, destroy the bunker”

Example

Input:
2
3 3 1
sss
ssX
Oss
3 3 3
Xss      
#s!
s!O
sss
#!s
!sO
ss!
#s!
ssO

Output:
3
4

Submit solution!

hide comments



	Simes: 2018-06-14 18:40:36 This is such a confusing problem statement. In the first example, it takes 3 "time steps" to reach the hostage, but the input time value is 1, and "Right after that maximum time the hostage will be killed". Shouldn't the hostage be dead by time step 3? After our hero takes the very first time step towards the hostage, hasn't the current time moved on? This would mean the current time is now 2, and so the next map should be used. Nope, apparently not. (Really nice subject matter too btw) Last edit: 2018-06-14 20:08:06
	:D: 2012-10-18 11:53:17 Ok, I will try to sum up the problem clarification. At every turn you can go in one of the 4 directions AND choose a time to go to (-1,0,+1 in respect to the current time). Description says you can't stay in the same spot, because it's never needed. That's not true! See the test case below: 2 3 3 X# !s O# s# !s O# s# s! O# If you can't stay in one spot, the answer will be “Hostage is death, destroy the bunker” otherwise 3. It seems that doesn't matter and I got AC with both versions. In short: test cases are VERY WEAK! Edit: when you move it is the only time you change times or you keep moving forward, i did not use a case like this and that is true, but cases are enough if you know the technique and you did understand the mechanic of the problem, then i think you deserve AC since this is classical but it is more like an introduction to this technique as when i did it i was a newbie doing this kind of problems :) but cases are weak that is so very true, i can't stand that almost anybody has tried haha! Last edit: 2012-10-27 01:04:28
	:D: 2012-08-13 08:30:06 So let me get this straight. At each step I make a move in one of the 4 directions AND choose go stay in the current time or go one minute forward or backward in time, right? In addition the field is available if there is no guard at a destination field in destination time. Source (field,time) state doesn't change. We are counting the number of such (field,time) turns. Correct me if I got something wrong. Also, there is a point in waiting at a current position, when you are blocked by the guards and need more than one time jump to escape. Last edit: 2012-08-13 08:32:52
	Luis Arguello: 2012-07-27 03:02:48 You have serious problems with the structure of the statement, please fix it. What happen with the X after time 1? It's an usable space? You can make steps in no time? Cause in the first case seems like you can. X after time 1 will never be visited again if you did your solution in the way it is supposed to, yeah you can cause you can make steps in the present :) Last edit: 2012-07-27 02:52:21

Submit solution!

Added by:	Rocker3011
Date:	2012-07-27
Time limit:	0.5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Own problem