#D. 星际探险家与麦当当

    远端评测题 2000ms 256MiB

星际探险家与麦当当

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

星际探险家在其最新的宇宙探险中遭遇了一系列新的挑战。此次探险中,探险家的飞船升级了,装备了最新的核能发动机。这意味着飞船不再需要依赖于星系门户中的充电桩进行能量补充。然而,这一新技术也带来了限制:每一次空间迁跃都只能固定跳跃kk个单位长度,不再能自由选择迁跃的距离。例如,如果当前探险家位于下标ii,那么他通过一次迁跃,可以抵达i+ki+kiki - k

探险家在穿越宇宙时,遇到了一个由神秘符号构成的空间区域。在这个区域中,

  • '.'代表空旷的太空,飞船可以安全的迁跃到这里;
  • 'G'表示星际探险家当前的位置;
  • 'T'代表目标位置,是一家遥远的星际麦当当,探险家的飞船需要到达这里。
  • 此外,这个空间中还散布着黑洞,用'#'表示。一旦探险家迁跃进入黑洞,他的探险将立即结束。

探险家的任务是判断是否存在一条安全的迁跃路径,使得他能够通过固定kk个单位的长度的迁跃,最终到达目标位置,而不会被黑洞吞噬。

输入格式

输入的第一行包含两个整数 nnkk2n1002 \leq n \leq 1001kn11 \leq k \leq n - 1) —— nn代表整个空间区域的全部空间个数,kk​代表探险家每次迁跃的固定距离。

第二行包含一个长度为 nn 的字符串,代表空间区域的构成。字符串由字符 '.', '#', 'G' 和 'T' 构成,分别代表空旷的太空、黑洞、探险家的当前位置和目标位置。输入字符串的长度不会超过100。

输出格式

输出应为"YES"或"NO"(不含引号)。如果探险家能够通过固定长度的迁跃安全到达目标位置,则输出"YES";如果无法到达或途中会落入黑洞,则输出"NO"。

样例数据

26 3
...#..T....#...#..G.#.....
NO
26 2
T..#..G....#...#....#.....
YES
26 1
G..T..#....#...#....#.....
YES

样例解释

  • 在第一个样例中,探险家向右走,第三次迁跃时会被从左往右数第三个黑洞所吞噬。
  • 在第二个样例中,探险家向左走,第三次会安全到达麦当当。
  • 在第三个样例中,尽管迁跃的长度是1,但由于路径上没有黑洞阻碍,探险家可以安全到达目标。

数据范围

对于100%100\%的数据满足:

  • 2n1002 \leq n \leq 100
  • 1kn11 \leq k \leq n - 1

2024年5月17日城阳区周赛-小学组

未参加
状态
已结束
规则
IOI
题目
4
开始于
2024-5-17 18:00
结束于
2024-5-20 0:00
持续时间
3 小时
主持人
参赛人数
20