← 返回题目列表

Codeforces · 1948/C

C. 箭头路径

中文机器翻译题面 查看原题

有一个网格,由 $$$2$$$ 行和 $$$n$$$ 列组成。行从上到下编号为 $$$1$$$ 到 $$$2$$$。这些列从左到右编号为 $$$1$$$ 到 $$$n$$$。网格的每个单元格都包含一个指向左侧或右侧的箭头。没有箭头指向网格之外。

有一个机器人在 $$$(1, 1)$$$ 单元格中启动。每一秒,以下两个动作相继发生:

1.首先,机器人向左、向右、向下、向上移动(不能尝试走出网格,也不能跳过移动);
2. 然后它沿着当前单元格(移动后最终到达的单元格)中放置的箭头移动。

你的任务是确定机器人是否可以到达单元格$$$(2, n)$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 ($$$2 \le n \le 2 \cdot 10^5$$$)。

第二行包含一个由 $$$n$$$ 个字符 < 和/或 > 组成的字符串 - 网格的第一行。

第三行包含一个由 $$$n$$$ 个字符 < 和/或 > 组成的字符串 - 网格的第二行。

输入的附加限制:

- $$$n$$$ 是偶数;
- 没有箭头指向网格之外;
- 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果机器人可以到达单元格 $$$(2, n)$$$,则打印 YES;否则,打印NO。

您可以在任何情况下打印每个字母。例如,yes、Yes、Yes 都会被识别为肯定答案。

示例

输入 #1

4
4
>><<
>>><
2
><
><
4
>>><
>><<
6
>><<><
><>>><

输出 #1

YES
YES
NO
YES

注意

在第一个示例中,其中一个可能的路径如下所示: $$$(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4)$$$。

在第二个示例中,可能的路径之一如下所示:$$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$$$。

在第三个示例中,无法到达单元格 $$$(2, 4)$$$。

在第四个示例中,可能的路径之一如下所示: $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (2, 5) \rightarrow (2, 6)$$$。