CF198B.Jumping on Walls

传统题 时间 2000 ms 内存 256 MiB 7 尝试 3 已通过 1 标签

Jumping on Walls

题目描述

瓦西亚在和忍者玩电脑游戏。在这个关卡,瓦西亚需要操控忍者走出一个很深的峡谷。

峡谷由两面垂直于地面且互相平行的墙组成,它们的高度为nn米。我们将这些墙分成许多11米长的区域,并从下到上用11nn的正整数对它们进行编号。有些地方是安全的,忍者可以爬上去。有些地方石头很尖锐,忍者不能待在那里。我们称这些地区为危险地区。

最初忍者在左墙的最下方。他每秒可以执行以下操作之一:

  • 向上爬一个区域;
  • 向下爬一个区域;
  • 跳到对面的墙上。忍者会跳到比他当前所在高度高kk米的地方。更准确地说,如果在跳跃之前忍者位于一面墙的区域xx,那么在跳跃之后,他位于另一面墙的区域x+kx + k

如果在某个时间点忍者到达了一个高度大于nn的区域,那么忍者就可以从峡谷中出来了。

但峡谷被水淹没了,每秒水位会上升一米。最初,水位达到区域11的下边界。忍者不能待在被水淹没的地方。忍者和水轮流移动——首先忍者行动,然后水上升一米,然后忍者再行动,以此类推。

如果忍者可以离开峡谷,那这个关卡就完成了。

在几次失败的尝试之后,瓦西亚开始怀疑是否有可能完成这一关卡。请回答他的问题。

输入格式

第一行包含两个整数nnkk (1n,k105)(1 \leq n ,k \leq 10^5)——峡谷的高度和忍者可以跳跃的高度

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

第三行以相同的格式描述了右墙。

数据保证左墙的第一个区域不是危险区域。

输出格式

如果忍者能从峡谷中出来,打印“YES”(不带引号),否则,打印“NO”(不带引号)。

说明/提示

在第一个样例中,忍者可以先跳到右边的墙,然后沿着右边的墙往下走一米,然后跳到左边的墙。再跳跃一次忍者就可以离开峡谷。

在第二个样例中,忍者是无法离开峡谷的。

样例

7 3
---X--X
-X--XX-
YES
6 2
--X-X-
X--XX-
NO

在线编程 IDE

建议全屏模式获得最佳体验