Turtle Mission: Robot and the Earthquake (Codeforces 1933F)
Tags: DP, shortest paths

The world is a grid with $$$n$$$ rows and $$$m$$$ columns. The rows are numbered $$$0, 1, \ldots, n-1$$$, while the columns are numbered $$$0, 1, \ldots, m-1$$$. In this world, the columns are cyclic (i.e. the top and the bottom cells in each column are adjacent). The cell on the $$$i$$$-th row and the $$$j$$$-th column ($$$0 \le i < n, 0 \le j < m$$$) is denoted as $$$(i,j)$$$. At time $$$0$$$, the cell $$$(i,j)$$$ (where $$$0 \le i < n, 0 \le j < m$$$) contains either a rock or nothing. The state of cell $$$(i,j)$$$ can be described using the integer $$$a_{i,j}$$$:   If $$$a_{i,j} = 1$$$, there is a rock at $$$(i,j)$$$.  If $$$a_{i,j} = 0$$$, there is nothing at $$$(i,j)$$$. As a result of aftershocks from the earthquake, the columns follow tectonic plate movements: each column moves cyclically upwards at a velocity of $$$1$$$ cell per unit of time. Formally, for some $$$0 \le i < n, 0 \le j < m$$$, if $$$(i,j)$$$ contains a rock at the moment, it will move from $$$(i, j)$$$ to $$$(i - 1, j)$$$ (or to $$$(n - 1, j)$$$ if $$$i=0$$$). The robot called RT is initially positioned at $$$(0,0)$$$. It has to go to $$$(n-1,m-1)$$$ to carry out an earthquake rescue operation (to the bottom rightmost cell). The earthquake doesn't change the position of the robot, they only change the position of rocks in the world.Let RT's current position be $$$(x,y)$$$ ($$$0 \le x < n, 0 \le y < m$$$), it can perform the following operations:   Go one cell cyclically upwards, i.e. from $$$(x,y)$$$ to $$$((x+n-1) \bmod n, y)$$$ using $$$1$$$ unit of time.  Go one cell cyclically downwards, i.e. $$$(x,y)$$$ to $$$((x+1) \bmod n, y)$$$ using $$$1$$$ unit of time.  Go one cell to the right, i.e. $$$(x,y)$$$ to $$$(x, y+1)$$$ using $$$1$$$ unit of time. (RT may perform this operation only if $$$y < m-1$$$.) Note that RT cannot go left using the operations nor can he stay at a position.Unfortunately, RT will explode upon colliding with a rock. As such, when RT is at $$$(x,y)$$$ and there is a rock at $$$((x+1) \bmod n, y)$$$ or $$$((x+2) \bmod n, y)$$$, RT cannot move down or it will be hit by the rock.   Similarly, if $$$y+1 < m$$$ and there is a rock at $$$((x+1) \bmod n, y+1)$$$, RT cannot move right or it will be hit by the rock.  However, it is worth noting that if there is a rock at $$$(x \bmod n, y+1)$$$ and $$$((x+1) \bmod n, y)$$$, RT can still move right safely.  Find the minimum amount of time RT needs to reach $$$(n-1,m-1)$$$ without colliding with any rocks. If it is impossible to do so, output $$$-1$$$.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.In each test case, the first line contains two integers $$$n$$$, $$$m$$$ ($$$3 \le n, m \le 10^3$$$) — the size of the planet's boundaries. Each of the next $$$n$$$ lines contains $$$m$$$ integers. The $$$(j+1)$$$-th integer on the $$$(i+1)$$$-th line ($$$0 \le i < n, 0 \le j < m$$$) is $$$a_{i,j}$$$ ($$$0 \le a_{i,j} \le 1$$$), which denotes whether or not there is a rock at $$$(i,j)$$$ at time $$$0$$$.Additionally, it is guaranteed that $$$a_{0,0} = 0$$$, and $$$a_{i, m-1} = 0$$$ for $$$0 \le i < n$$$. In other words, there is no rock at RT's initial position as well as column $$$m-1$$$.The sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case:   If the destination can be reached without colliding with any rocks, output a single integer — the minimum amount of time RT needs to reach $$$(n-1,m-1)$$$.  Otherwise, output $$$-1$$$. 

Note: Visual explanation of the first test case in the example:   

Sample Inputs:
6
4 5
0 1 0 0 0
0 0 1 0 0
1 0 1 1 0
0 0 0 0 0
3 3
0 0 0
1 0 0
0 0 0
5 3
0 0 0
0 0 0
1 0 0
0 0 0
1 0 0
3 7
0 0 1 0 0 1 0
1 0 1 0 1 0 0
0 1 0 0 0 0 0
3 4
0 1 0 0
1 0 0 0
0 1 1 0
5 5
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0

6
3 3
0 0 0
0 0 0
0 0 0
4 3
0 1 0
1 0 0
0 1 0
1 0 0
4 3
0 1 0
0 1 0
0 1 0
0 1 0
3 3
0 0 0
1 1 0
0 0 0
3 3
0 1 0
0 0 0
0 1 0
5 5
0 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 1 0 0

Sample Outputs:
7
3
3
8
-1
12

3
3
-1
-1
3
8

Solution (Python):
from collections import deque
import sys
INF = float('inf')

def solve(Mat, row, col):
    li = deque()
    li.append((0, 0))
    dist = [[INF] * col for i in range(row)]
    dist[0][0] = 0
    (pre, suff) = ([0], [Mat[row - 1][col - 1]])
    for r in range(row):
        pre.append(pre[-1] + Mat[r][col - 1])
    for r in range(row - 2, -1, -1):
        suff.append(Mat[r][col - 1])
    suff.reverse()
    ans = INF
    while len(li):
        (x, y) = li.popleft()
        if y == col - 1:
            end = (dist[x][y] - 1) % row
            wait = (x - end) % row
            chase = INF
            gap = (end - x) % row
            if x <= end:
                obs = pre[end + 1] - pre[x]
                if obs == 0:
                    chase = gap
            else:
                obs = suff[x] + pre[end + 1]
                if obs == 0:
                    chase = gap
            stepsTaken = dist[x][y] + min(chase, wait)
            ans = min(ans, stepsTaken)
            continue
        (nx, ny) = ((x + 2) % row, y)
        if dist[nx][ny] > dist[x][y] + 1 and Mat[(x + 1) % row][y] == Mat[nx][ny] == 0:
            dist[nx][ny] = dist[x][y] + 1
            li.append((nx, ny))
        (nx, ny) = ((x + 1) % row, (y + 1) % col)
        if dist[nx][ny] > dist[x][y] + 1 and Mat[nx][ny] == 0:
            dist[nx][ny] = dist[x][y] + 1
            li.append((nx, ny))
    if ans == INF:
        return -1
    return ans
for case in range(int(input())):
    (n, m) = map(int, input().split())
    M = []
    for i in range(n):
        li = list(map(int, input().split()))
        M.append(li)
    print(solve(M, n, m))

Solution (Python):
from collections import *
from itertools import *
from bisect import *
from heapq import *
from math import ceil, prod, gcd
mod = 10 ** 9 + 7
d = ((1, 0), (0, 1), (0, -1), (-1, 0))
alpha = 'abcdefghijklmnopqrstuvwxyz'

def helper():
    res = float('inf')
    visited = set()
    bfs = deque([(0, 0, 0)])
    while bfs:
        (i, j, time) = bfs.popleft()
        if (i, j) in visited:
            continue
        visited.add((i, j))
        if j == m - 1:
            temp = abs((time - 1) % n - i)
            res = min(res, time + min(temp, n - temp))
        k = (i + 1) % n
        if j < m - 1 and grid[k][j + 1] == 0:
            bfs.append((k, j + 1, time + 1))
        l = (i + 2) % n
        if grid[k][j] == grid[l][j] == 0:
            bfs.append((l, j, time + 1))
    return res if res != float('inf') else -1
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    grid = []
    for _ in range(n):
        grid.append(list(map(int, input().split())))
    print(helper())

Solution (Python):
from sys import stdin
from collections import deque
input = lambda : stdin.buffer.readline().decode().strip()
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    g = [list(map(int, input().split())) for _ in range(n)]
    ans = inf = 1 << 60
    vis = [[0] * m for _ in range(n)]
    bfs = deque([(0, 0, 0)])
    vis[0][0] = 1
    while bfs:
        (i, j, t) = bfs.popleft()
        if j == m - 1:
            ans = t + min((i - t) % n + 1, n - 1 - (i - t) % n)
            break
        if g[(i + 1) % n][(j + 1) % m] == 0 and (not vis[(i + 1) % n][(j + 1) % m]):
            vis[(i + 1) % n][(j + 1) % m] = 1
            bfs += [((i + 1) % n, (j + 1) % m, t + 1)]
        if g[(i + 1) % n][j] == g[(i + 2) % n][j] == 0 and (not vis[(i + 2) % n][j]):
            vis[(i + 2) % n][j] = 1
            bfs += [((i + 2) % n, j, t + 1)]
    print(ans if ans < inf else -1)