ROT - Rescue On Time
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
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?
|
|
: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:
|
|
: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.
|
|
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.
|
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 |