SPIDY - Spiderman vs Sandman
There is a faceoff between Spiderman & Sandman.
There are two glass buildings each of height H. Each building has H equal sized windows on the outside covering entire space from bottom to top. Some windows are open and spiderman cannot land on these window.
In one step, Spiderman can:
1) Rise up to just above window of the same building he is on.
2) Slide down to just below window of the same building he is on.
3) Use his web to jump to Kth window above from current height on the other building.
Sandman on the other rises steadily a rate of 1 per step.
For the purpose of this problem, assume Spiderman and Sandman take turns ie: Spiderman takes one step, then Sandman takes one step.
Your goal is to assist Spiderman to always remain above or at same height as Sandman at the end of Sandman's turn. Spiderman gets the first turn and both start at height 0 (ie: Sandman is on the ground and Spiderman is on the window of lowermost floor of left building. It is guarenteed that window of lowermost floor of left building is not open.
Note : If Spiderman gets to area with height >= H assume he has got out.
You are Spiderman's best friend, your duty is to guide Spiderman to escape from Sandman if possible in shortest number of steps to get out.
First line contains integer T.
T Testcases follow. Each testcase contains 3 lines.
First line of input contains two space seperated integers H & K
Next two lines contain description of two buildings.
2nd line represents the left building - a string of length H. The ith character represents the state of window between (i-1) and i heights : character '-' represents closed window(safe to land on) , character 'X' represents open window.
Similarly 3rd line represents the right building.
For every testcase output single integer x where x is the number of steps taken to get out of building. Output "NO" if Spiderman cannot escape the area and has to fight in the enclosure.
1 <= H,K <= 10^5
In first case Spiderman jumps to right building, goes one height down, jumps to left building and jumps to right buidling (he got to the top).
In second case, no matter how he moves, Spiderman cannot escape above the buildings.
My god, this problem gave me headaches. Be advised to consider these examples:
Just a little clarification (cause I got WA for misunderstanding): windows are at heights 0 to H-1, Spiderman escapes if he reaches a point beyond the buildings.
Any Special test cases :P
Finally AC ;)
Prajwal A N:
In the problem statement the 3rd kind of move of superman states that
Chow-shing Shi :: The idea is from there, I agree. But the problem was used as a tutorial for graph algorithms as a practice for upcoming ACM ICPC in an institutional contest, and the problem provided an excellent source for the same. Nonetheless, problem description, output values, and test cases have been kept different.
copied from codeforces~~~~
AC...question is a little tricky :)Last edit: 2012-09-25 06:03:14
@dexter: consider him escaped if he jumps to height > h (as a result of a one unit jump from height h or from a k unit jump from opposite building from height > h-k)