Arrow Path (Codeforces 1948C)
Tags: Others, shortest paths

There is a grid, consisting of $$$2$$$ rows and $$$n$$$ columns. The rows are numbered from $$$1$$$ to $$$2$$$ from top to bottom. The columns are numbered from $$$1$$$ to $$$n$$$ from left to right. Each cell of the grid contains an arrow pointing either to the left or to the right. No arrow points outside the grid.There is a robot that starts in a cell $$$(1, 1)$$$. Every second, the following two actions happen one after another:   Firstly, the robot moves left, right, down or up (it can't try to go outside the grid, and can't skip a move);  then it moves along the arrow that is placed in the current cell (the cell it ends up after its move). Your task is to determine whether the robot can reach the cell $$$(2, n)$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer ($$$2 \le n \le 2 \cdot 10^5$$$).The second line contains a string consisting of exactly $$$n$$$ characters < and/or > — the first row of the grid.The third line contains a string consisting of exactly $$$n$$$ characters < and/or > — the second row of the grid.Additional constraints on the input:   $$$n$$$ is even;  there are no arrows pointing outside the grid;  the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$. 

Output: For each test case, print YES if the robot can reach the cell $$$(2, n)$$$; otherwise, print NO.You can print each letter in any case. For example, yes, Yes, YeS will all be recognized as positive answer.

Note: In the first example, one of the possible paths looks as follows: $$$(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4)$$$.In the second example, one of the possible paths looks as follows: $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$$$.In the third example, there is no way to reach the cell $$$(2, 4)$$$.In the fourth example, one of the possible paths looks as follows: $$$(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)$$$.

Sample Inputs:
4
4
>><<
>>><
2
><
><
4
>>><
>><<
6
>><<><
><>>><

Sample Outputs:
YES
YES
NO
YES

Solution (Python):
import sys
infile = sys.stdin
input = lambda : infile.readline().rstrip()
for _ in range(int(input())):
    n = int(input())
    R1 = input()
    R2 = input()
    wayOk = n == 2 or (all((a == '>' or b == '>' for (a, b) in zip(R1[1::2], R2[:-2:2]))) and all((a == '>' or b == '>' for (a, b) in zip(R1[1::2], R2[2::2]))))
    print('YES' if wayOk and R2[-2] == '>' else 'NO')

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    path = [input()[:-1] for _ in range(2)]
    if path[1][-2] == '<':
        print('NO')
        continue
    (x, y) = (1, n - 2)
    while y > 0:
        if path[x ^ 1][y - 1] == '>':
            x ^= 1
            y -= 1
        elif y >= 2 and path[x][y - 2] == '>':
            y -= 2
        else:
            print('NO')
            break
    else:
        print('YES')

Solution (Python):
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    a1 = input()
    a2 = input()
    p = (1, 1)
    for i in range(n):
        if a2[n - 2] == '<':
            ans.append('NO')
            break
        elif i % 2 == 0:
            if a2[i] == '<' and a1[i + 1] == '<':
                ans.append('NO')
                break
            elif a2[i] == '<' and a1[i - 1] == '<':
                ans.append('NO')
                break
    else:
        ans.append('YES')
for i in range(t):
    print(ans[i])