Computer Game (Codeforces 1598A)
Tags: DP, dfs and similar

Monocarp is playing a computer game. Now he wants to complete the first level of this game.A level is a rectangular grid of $$$2$$$ rows and $$$n$$$ columns. Monocarp controls a character, which starts in cell $$$(1, 1)$$$ — at the intersection of the $$$1$$$-st row and the $$$1$$$-st column.Monocarp's character can move from one cell to another in one step if the cells are adjacent by side and/or corner. Formally, it is possible to move from cell $$$(x_1, y_1)$$$ to cell $$$(x_2, y_2)$$$ in one step if $$$|x_1 - x_2| \le 1$$$ and $$$|y_1 - y_2| \le 1$$$. Obviously, it is prohibited to go outside the grid.There are traps in some cells. If Monocarp's character finds himself in such a cell, he dies, and the game ends.To complete a level, Monocarp's character should reach cell $$$(2, n)$$$ — at the intersection of row $$$2$$$ and column $$$n$$$.Help Monocarp determine if it is possible to complete the level.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then the test cases follow. Each test case consists of three lines.The first line contains a single integer $$$n$$$ ($$$3 \le n \le 100$$$) — the number of columns.The next two lines describe the level. The $$$i$$$-th of these lines describes the $$$i$$$-th line of the level — the line consists of the characters '0' and '1'. The character '0' corresponds to a safe cell, the character '1' corresponds to a trap cell.Additional constraint on the input: cells $$$(1, 1)$$$ and $$$(2, n)$$$ are safe.

Output: For each test case, output YES if it is possible to complete the level, and NO otherwise.

Note: Consider the example from the statement.In the first test case, one of the possible paths is $$$(1, 1) \rightarrow (2, 2) \rightarrow (2, 3)$$$.In the second test case, one of the possible paths is $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 3) \rightarrow (2, 4)$$$.In the fourth test case, one of the possible paths is $$$(1, 1) \rightarrow (2, 2) \rightarrow (1, 3) \rightarrow (2, 4) \rightarrow (1, 5) \rightarrow (2, 6)$$$.

Sample Inputs:
4
3
000
000
4
0011
1100
4
0111
1110
6
010101
101010

Sample Outputs:
YES
YES
NO
YES

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    row1 = input()
    row2 = input()
    flag = 0
    for i in range(n):
        if row1[i] == '1' and row2[i] == '1':
            flag = 1
            break
    if flag == 1:
        print('NO')
    else:
        print('YES')

Solution (Python):
def is_possible_to_complete_level(n, level):
    dp = [[False] * n for _ in range(2)]
    dp[0][0] = True
    for j in range(1, n):
        if level[0][j] == '0' and (dp[0][j - 1] or dp[1][j - 1]):
            dp[0][j] = True
        if level[1][j] == '0' and (dp[0][j - 1] or dp[1][j - 1] or dp[1][j]):
            dp[1][j] = True
    return 'YES' if dp[1][n - 1] else 'NO'
t = int(input())
for _ in range(t):
    n = int(input())
    level = [input() for _ in range(2)]
    result = is_possible_to_complete_level(n, level)
    print(result)

Solution (Python):
def solve():
    n = int(input())
    s1 = input()
    s2 = input()
    ne = 0
    bad = False
    for i in range(n):
        bad |= s1[i] == '1' and s2[i] == '1'
    if bad:
        print('NO')
    else:
        print('YES')
t = int(input())
for i in range(t):
    solve()