C. 箭头路径 详细题解

题目核心理解

有一个 $2$ 行 $n$ 列的网格，每个格子有向左 < 或向右 > 的箭头，且箭头不会指向网格外。 机器人从格子 $(1,1)$ 出发，每一秒按顺序执行两步：

1. 先自主向上下左右某一方向移动一格（不能出界、不能不动）；
2. 再沿着当前所在格子的箭头方向移动一格。

问机器人是否可以到达终点 $(2,n)$。

---

核心思路

1. 关键性质

按格子坐标 $(r,c)$ 的和 $r+c$ 的奇偶性，把格子分为两类：

• 偶格：$r+c$ 为偶数，只能在箭头移动后停留；
• 奇格：$r+c$ 为奇数，只能在自主移动后停留。 机器人始终在两类格子之间交替到达，不会停留在同类格子。

2. 判定规则

唯一会卡死机器人的情况： 存在偶数列 $c$，满足同一列的两个奇格 $(1,c)$ 和 $(2,c)$ 内的箭头都是向左 <。 只要出现这样一对位置，答案就是 $\text{NO}$； 其余所有情况都可以顺利走到终点，答案为 $\text{YES}$。

---

算法流程

1. 读入 $n$ 以及两行箭头字符串；
2. 遍历所有偶数列（下标从 $0$ 开始时为 $1,3,5,\dots$）；
3. 若某一列中两个字符均为 <，直接判定无解；
4. 遍历完成未发现卡死点，则判定有解。

---

公式与复杂度分析

无解判定条件：

$$\exists c \text{ 为偶数},\ \ s_1[c] = \texttt{<}\ \ \text{且}\ \ s_2[c] = \texttt{<} $$

复杂度

每组测试用例只需要一次线性遍历。 时间复杂度：$O(n)$。 总复杂度满足 $\sum n \le 2\cdot 10^5$，可在时限内轻松运行。