Railguns (Codeforces 1840F)
Tags: DP, dfs and similar

Tema is playing a very interesting computer game.During the next mission, Tema's character found himself on an unfamiliar planet. Unlike Earth, this planet is flat and can be represented as an $$$n \times m$$$ rectangle.Tema's character is located at the point with coordinates $$$(0, 0)$$$. In order to successfully complete the mission, he needs to reach the point with coordinates $$$(n, m)$$$ alive.Let the character of the computer game be located at the coordinate $$$(i, j)$$$. Every second, starting from the first, Tema can:  either use vertical hyperjump technology, after which his character will end up at coordinate $$$(i + 1, j)$$$ at the end of the second;  or use horizontal hyperjump technology, after which his character will end up at coordinate $$$(i, j + 1)$$$ at the end of the second;  or Tema can choose not to make a hyperjump, in which case his character will not move during this second; The aliens that inhabit this planet are very dangerous and hostile. Therefore, they will shoot from their railguns $$$r$$$ times.Each shot completely penetrates one coordinate vertically or horizontally. If the character is in the line of its impact at the time of the shot (at the end of the second), he dies.Since Tema looked at the game's source code, he knows complete information about each shot — the time, the penetrated coordinate, and the direction of the shot.What is the minimum time for the character to reach the desired point? If he is doomed to die and cannot reach the point with coordinates $$$(n, m)$$$, output $$$-1$$$.

Input: The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.Then follow the descriptions of the test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 10^4$$$) — the size of the planet, its height and width.The second line of each test case contains a single integer $$$r$$$ ($$$1 \le r \le 100$$$) — the number of shots.Then follow $$$r$$$ lines, each describing one shot.A shot is described by three integers $$$t$$$, $$$d$$$, $$$coord$$$. Where $$$t$$$ is the second at which the shot will be fired ($$$1 \le t \le 10^9$$$). $$$d$$$ is the direction of the shot ($$$d = 1$$$ denotes a horizontal shot, $$$d = 2$$$ denotes a vertical shot). $$$coord$$$ is the size of the penetrated coordinate ($$$0 \le coord \le n$$$ for $$$d = 1$$$, $$$0 \le coord \le m$$$ for $$$d = 2$$$).The sum of the products $$$n \cdot m$$$ over all test cases does not exceed $$$10^4$$$.

Output: For each test case, output a single number — the minimum time for the character to reach the coordinate $$$(n, m)$$$, or $$$-1$$$ if he is doomed to die.

Note: In the first test case, the character can move as follows: $$$(0, 0) \rightarrow (0, 1) \rightarrow (0, 2) \rightarrow (0, 3) \rightarrow (0, 3) \rightarrow (1, 3)$$$.In the second test case, the character will not be able to leave the rectangle that will be completely penetrated by shots at the second $$$2$$$.

Sample Inputs:
5
1 3
4
1 2 0
2 2 1
3 2 2
4 1 1
3 3
6
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2
2 1
3
7 1 2
2 1 1
7 2 1
2 2
5
9 1 2
3 2 0
5 1 2
4 2 2
7 1 0
4 6
7
6 1 2
12 1 3
4 1 0
17 2 3
1 2 6
16 2 6
3 2 4

Sample Outputs:
5
-1
3
6
10

Solution (Python):
import io
import os
import sys
from collections import deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    r = int(input())
    rays = []
    for _ in range(r):
        rays += [tuple(map(int, input().split()))]
    rays.sort(reverse=True)
    planet = [[None] * (m + 1) for _ in range(n + 1)]
    planet[0][0] = 0
    second = 0
    queue = deque()
    queue.append((0, 0, 0))
    while True:
        second += 1
        while len(queue) > 0:
            (s, y, x) = queue.popleft()
            if s > second:
                queue.appendleft((s, y, x))
                break
            neighbors = [(y + 1, x), (y, x + 1), (y, x)]
            for (ii, jj) in neighbors:
                if ii <= n and jj <= m:
                    if planet[ii][jj] is None:
                        planet[ii][jj] = second
                        queue.append((second + 1, ii, jj))
        while len(rays) > 0:
            if rays[-1][0] == second:
                queue.clear()
                (_, d, coord) = rays.pop()
                if d == 1:
                    for j in range(m + 1):
                        planet[coord][j] = None
                elif d == 2:
                    for i in range(n + 1):
                        planet[i][coord] = None
            else:
                break
        if planet[n][m] is not None:
            sys.stdout.write(f'{second}\n')
            break
        if len(queue) == 0:
            for i in range(n + 1):
                for j in range(m + 1):
                    if planet[i][j] is not None:
                        queue.append((second, i, j))
        if len(queue) == 0:
            sys.stdout.write('-1\n')
            break

Solution (Python):
""""""
from collections import deque

def main():
    inf = 100000

    def march_forward(can_occupy, dt):
        """"""
        q = deque()
        for i in range(n + 1):
            for j in range(m + 1):
                if can_occupy[i * (m + 1) + j] == 1:
                    q.append((i, j, dt))
        while q:
            (i, j, steps_left) = q.popleft()
            if steps_left - 1 >= 0:
                for (ii, jj) in ((i + 1, j), (i, j + 1)):
                    if ii <= n and jj <= m and (can_occupy[ii * (m + 1) + jj] == 0):
                        can_occupy[ii * (m + 1) + jj] = 1
                        q.append((ii, jj, steps_left - 1))
        return None

    def min_steps_to_end(can_occupy):
        min_steps = inf
        for i in range(n + 1):
            for j in range(m + 1):
                if can_occupy[i * (m + 1) + j] == 1:
                    min_steps = min(min_steps, n - i + m - j)
        return min_steps
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m) = readIntArr()
        r = int(input())
        t_d_c = []
        for __ in range(r):
            t_d_c.append(readIntArr())
        t_d_c.sort(key=lambda arr: arr[0])
        can_occupy = [0] * ((n + 1) * (m + 1))
        can_occupy[0] = 1
        ans = -1
        time = 0
        ti = 0
        while True:
            while ti < r and t_d_c[ti][0] == time:
                if t_d_c[ti][1] == 1:
                    for j in range(m + 1):
                        can_occupy[t_d_c[ti][2] * (m + 1) + j] = 0
                else:
                    for i in range(n + 1):
                        can_occupy[i * (m + 1) + t_d_c[ti][2]] = 0
                ti += 1
            min_steps = min_steps_to_end(can_occupy)
            if min_steps == inf:
                break
            if ti < r and t_d_c[ti][0] - time > min_steps or ti == r:
                ans = time + min_steps
                break
            dt = t_d_c[ti][0] - time
            march_forward(can_occupy, dt)
            time = t_d_c[ti][0]
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
from collections import defaultdict
from sys import stdin

def solve2(rows, cols, r, h_shots, v_shots):
    dp = [[[False] * (r + 1) for _ in range(cols + 1)] for _ in range(rows + 1)]
    dp[0][0][0] = True
    for i in range(rows + 1):
        for j in range(cols + 1):
            for k in range(r + 1):
                t = k + i + j
                if t not in h_shots[i] and t not in v_shots[j]:
                    if i and dp[i - 1][j][k]:
                        dp[i][j][k] = True
                    if j and dp[i][j - 1][k]:
                        dp[i][j][k] = True
                    if k and dp[i][j][k - 1]:
                        dp[i][j][k] = True
    ans = -1
    for i in range(r, -1, -1):
        if dp[rows][cols][i]:
            ans = rows + cols + i
    return ans
ans = []
for _ in range(int(stdin.readline())):
    (rows, cols) = map(int, stdin.readline().split())
    v_shots = defaultdict(set)
    h_shots = defaultdict(set)
    r = int(stdin.readline())
    for _ in range(r):
        (t, d, coord) = map(int, stdin.readline().split())
        if d == 1:
            h_shots[coord].add(t)
        else:
            v_shots[coord].add(t)
    ans.append(solve2(rows, cols, r, h_shots, v_shots))
print('\n'.join(map(str, ans)))