SPIDY - Spiderman vs Sandman

no tags 

 

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.

 

Input

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.

 

Output

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.

 

Constraints

1<=T<=10

1 <= H,K <= 10^5

 

Example

Input: 

2

7 3

---X--X

-X--XX-

6 2

--X-X-

X--XX-

 

Output: 

4

NO

 

EXPLANATION

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.

 


hide comments
enigmus: 2016-02-17 13:53:21

My god, this problem gave me headaches. Be advised to consider these examples:
(10, 3)
-------x-x
xxx-x-x-xx
Answear: 5

(8, 3)
---xxxxx
xxx-x-xx
Answear: 4

Good luck!

Last edit: 2016-02-17 13:53:45
hodobox: 2015-12-12 00:33:46

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.

Malena: 2014-02-09 21:26:29

Any Special test cases :P

technophyle: 2013-02-03 15:20:04

Finally AC ;)
I was printing 'YES' instead of actual distance. :p
RE: Don't be too codeforcy :P

Last edit: 2013-06-04 06:50:25
Prajwal A N: 2013-02-03 15:20:04

In the problem statement the 3rd kind of move of superman states that
"3. Use his web to jump to Kth window above from current height on the other building."
If spiderman is on ith window (i=1,2,...,h) then is he at height i-1 or at height i?
If he is at height i-1 (as the statement - "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."), then how can spiderman climb down a window in the first testcase after jumping to the 3rd window on the right building.
If he is at height i then the answer for the second test case should be 5.
Can someone clarify if the question is wrong or am I going wrong somewhere.

Piyush Kumar: 2013-02-03 15:20:04

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.

Zhouxing Shi: 2013-02-03 15:20:04

copied from codeforces~~~~

Archit Mittal: 2013-02-03 15:20:04

AC...question is a little tricky :)

Last edit: 2012-09-25 06:03:14
Piyush Kumar: 2013-02-03 15:20:04

@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)


Added by:Anil Shanbhag
Date:2012-09-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:codeforces