题目描述

Vasya plays a computer game with ninjas. At this stage Vasya's ninja should get out of a deep canyon.

The canyon consists of two vertical parallel walls, their height is n meters. Let's imagine that we split these walls into 1 meter-long areas and number them with positive integers from 1 to n from bottom to top. Some areas are safe and the ninja can climb them. Others are spiky and ninja can't be there. Let's call such areas dangerous.

Initially the ninja is on the lower area of the left wall. He can use each second to perform one of the following actions:

• climb one area up;
• climb one area down;
• jump to the opposite wall. That gets the ninja to the area that is exactly k meters higher than the area he jumped from. More formally, if before the jump the ninja is located at area x of one wall, then after the jump he is located at area x + k of the other wall.

If at some point of time the ninja tries to get to an area with a number larger than n, then we can assume that the ninja got out of the canyon.

The canyon gets flooded and each second the water level raises one meter. Initially the water level is at the lower border of the first area. Ninja cannot be on the area covered by water. We can assume that the ninja and the water "move in turns" — first the ninja performs some action, then the water raises for one meter, then the ninja performs one more action and so on.

The level is considered completed if the ninja manages to get out of the canyon.

After several failed attempts Vasya started to doubt whether it is possible to complete the level at all. Help him answer the question.

Vasya和忍者玩电脑游戏。在这个阶段，瓦斯亚的忍者应该走出一个深峡谷。

峡谷由两个垂直平行的墙壁组成，它们的高度是n米。让我们想象一下，我们把这些墙分成1米长的区域，从下到上用1到n的正整数来编号。有些区域是安全的，忍者可以爬上去。其他的是尖刺的，忍者不能在那里。让我们称这些地区为危险地区。

一开始忍者是在左边墙的下部。他可以利用每一秒执行以下动作之一:

向上攀爬一个区域;
往下爬一个区域;
跳到对面的墙上。这让忍者到达了比他跳的地方高k米的地方。更正式地说，如果在跳跃之前，忍者位于一面墙的x区域，那么在跳跃之后，他位于另一面墙的x + k区域。
如果在某个时间点，忍者试图到达一个数字大于n的区域，那么我们可以假设忍者已经离开了峡谷。

峡谷被淹没，水位每秒钟上升一米。最初，水位在第一个区域的下界。忍者不能出现在被水覆盖的区域。我们可以假设忍者和水“轮流移动”——首先忍者执行一些动作，然后水上升1米，然后忍者再执行一个动作，以此类推。

如果忍者成功逃出峡谷，这一关就算是通关了。

在几次失败的尝试后，Vasya开始怀疑是否有可能完成这一关。帮他回答这个问题

第一行包含两个整数n和k(1≤n, k≤105)——峡谷的高度和忍者跳跃的高度。

第二行包含左墙的描述—长度为n个字符的字符串。第i个字符表示第i个墙区域的状态:字符“X”表示危险区域，字符“-”表示安全区域。

第三行用同样的格式描述了右边的墙。

保证左墙的第一个区域没有危险。

题目分析

有左边A 右边B 两面墙，将墙视作两条长度为n米的线段
每1m为一个部分，这个部分可能是尖刺或者安全
忍者可以选择向上爬、向下爬、或者跳到对面的墙壁（跳越会有跳跃高度，即在i位置则跳到另一墙的i+k位置）
每次行动水位会上升1m，若淹没忍者，则失败

分析例子：
（左墙1 右墙2）

7 3 墙高7m，忍者可以跳跃3m
则可以通关的路径为：（为了避免忍者被水淹没，优先选择跳跃前进）
墙 高 水位
1 1 0
2 4 1 从左墙跳到右墙
2 3 2 右墙向下爬1m
1 6 3 右墙跳到左墙
2 9 4（9>7)通关

6 2 墙高6m，忍者可以跳跃2m
则可以通关的路径为：
墙 高 水位
1 1 0
2 3 1 左墙跳到右墙
2 2 2 （2>=2)右墙向下爬1m后被水淹没
1 5 2 该位置为尖刺，被戳死
2 4 2 该位置为尖刺，被戳死
综上所述，该例子无通关路径

思路

根据特点判断：迷宫 最快走出 ————深度优先遍历