Bouncy Ball (Codeforces 1807F)
Tags: Implement, dfs and similar

You are given a room that can be represented by a $$$n \times m$$$ grid. There is a ball at position $$$(i_1, j_1)$$$ (the intersection of row $$$i_1$$$ and column $$$j_1$$$), and it starts going diagonally in one of the four directions:  The ball is going down and right, denoted by $$$\texttt{DR}$$$; it means that after a step, the ball's location goes from $$$(i, j)$$$ to $$$(i+1, j+1)$$$.  The ball is going down and left, denoted by $$$\texttt{DL}$$$; it means that after a step, the ball's location goes from $$$(i, j)$$$ to $$$(i+1, j-1)$$$.  The ball is going up and right, denoted by $$$\texttt{UR}$$$; it means that after a step, the ball's location goes from $$$(i, j)$$$ to $$$(i-1, j+1)$$$.  The ball is going up and left, denoted by $$$\texttt{UL}$$$; it means that after a step, the ball's location goes from $$$(i, j)$$$ to $$$(i-1, j-1)$$$. After each step, the ball maintains its direction unless it hits a wall (that is, the direction takes it out of the room's bounds in the next step). In this case, the ball's direction gets flipped along the axis of the wall; if the ball hits a corner, both directions get flipped. Any instance of this is called a bounce. The ball never stops moving.  In the above example, the ball starts at $$$(1, 7)$$$ and goes $$$\texttt{DL}$$$ until it reaches the bottom wall, then it bounces and continues in the direction $$$\texttt{UL}$$$. After reaching the left wall, the ball bounces and continues to go in the direction $$$\texttt{UR}$$$. When the ball reaches the upper wall, it bounces and continues in the direction $$$\texttt{DR}$$$. After reaching the bottom-right corner, it bounces once and continues in direction $$$\texttt{UL}$$$, and so on.Your task is to find how many bounces the ball will go through until it reaches cell $$$(i_2, j_2)$$$ in the room, or report that it never reaches cell $$$(i_2, j_2)$$$ by printing $$$-1$$$.Note that the ball first goes in a cell and only after that bounces if it needs to.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The first line of each test case contains six integers and a string $$$n, m, i_1, j_1, i_2, j_2, d$$$ ($$$2 \leq n, m \leq 25000$$$; $$$1 \leq i_1, i_2 \leq n$$$; $$$1 \leq j_1, j_2 \leq m$$$; $$$d \in\{ \texttt{DR}, \texttt{DL}, \texttt{UR}, \texttt{UL}\}$$$) — the dimensions of the grid, the starting coordinates of the ball, the coordinates of the final cell and the starting direction of the ball.It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$.

Output: For each test case, output a single integer — the number of bounces the ball does until it reaches cell $$$(i_2, j_2)$$$ for the first time, or $$$-1$$$ if the ball never reaches the final cell.


Sample Inputs:
6
5 7 1 7 2 4 DL
5 7 1 7 3 2 DL
3 3 1 3 2 2 UR
2 4 2 1 2 2 DR
4 3 1 1 1 3 UL
6 4 1 2 3 4 DR

Sample Outputs:
3
-1
1
-1
4
0

Solution (Python):
t = int(input())
for _ in range(t):
    inp = input().split()
    d = inp[-1]
    (n, m, i1, j1, i2, j2) = [int(x) for x in inp[:-1]]
    x = [-1, 1][d[1] == 'R']
    y = [-1, 1][d[0] == 'D']
    x0 = x
    y0 = y
    ic = i1
    jc = j1
    steps = 0
    while 1:
        if ic == i2 and jc == j2:
            print(steps)
            break
        b = False
        if ic + y == 0:
            y = 1
            b = True
        elif ic + y == n + 1:
            y = -1
            b = True
        if jc + x == 0:
            x = 1
            b = True
        elif jc + x == m + 1:
            x = -1
            b = True
        steps += b
        ic += y
        jc += x
        if ic == i1 and jc == j1 and (x == x0 or jc == 1 or jc == m) and (y == y0 or ic == 1 or ic == n):
            print(-1)
            break

Solution (Python):
t = int(input())
for _ in range(t):
    field = input().split()
    d = field[-1]
    (n, m, i1, j1, i2, j2) = [int(x) for x in field[:-1]]
    x = [-1, 1][d[1] == 'R']
    y = [-1, 1][d[0] == 'D']
    x0 = x
    y0 = y
    ic = i1
    jc = j1
    steps = 0
    while True:
        if ic == i2 and jc == j2:
            print(steps)
            break
        boolI = False
        if ic + y == 0:
            y = 1
            boolI = True
        elif ic + y == n + 1:
            y = -1
            boolI = True
        if jc + x == 0:
            x = 1
            boolI = True
        elif jc + x == m + 1:
            x = -1
            boolI = True
        steps += boolI
        ic += y
        jc += x
        if ic == i1 and jc == j1 and (x == x0 or jc == 1 or jc == m) and (y == y0 or ic == 1 or ic == n):
            print(-1)
            break

Solution (Python):
t = int(input())
for _ in range(t):
    inp = input().split()
    d = inp[-1]
    (n, m, i1, j1, i2, j2) = [int(x) for x in inp[:-1]]
    x = [-1, 1][d[1] == 'R']
    y = [-1, 1][d[0] == 'D']
    x0 = x
    y0 = y
    ic = i1
    jc = j1
    steps = 0
    while 1:
        if ic == i2 and jc == j2:
            print(steps)
            break
        b = False
        if ic + y == 0:
            y = 1
            b = True
        elif ic + y == n + 1:
            y = -1
            b = True
        if jc + x == 0:
            x = 1
            b = True
        elif jc + x == m + 1:
            x = -1
            b = True
        steps += b
        ic += y
        jc += x
        if ic == i1 and jc == j1 and (x == x0 or jc == 1 or jc == m) and (y == y0 or ic == 1 or ic == n):
            print(-1)
            break