Hypyt

from collections import deque
import sys

Pos = tuple[int, int]

def one_jump_gap(a: Pos, b: Pos) -> bool:
    return a[0] == b[0] or a[1] == b[1]

def two_jump_gap(board: list[list[bool]], a: Pos, b: Pos) -> bool:
    return not board[a[0]][b[1]] or not board[b[0]][a[1]]

def breadth_first(board: list[list[bool]], start: Pos, end: Pos, n: int, m: int) -> int:
    if start == end:
        return 0
    if one_jump_gap(start, end):
        return 1
    if two_jump_gap(board, start, end):
        return 2

    queue = deque([start])

    # bitsets for visited rows and columns
    rows_mask = 0
    cols_mask = 0

    def set_row(i: int):
        nonlocal rows_mask
        rows_mask |= 1 << i

    def set_col(j: int):
        nonlocal cols_mask
        cols_mask |= 1 << j

    def is_row_set(i: int) -> bool:
        return (rows_mask >> i) & 1

    def is_col_set(j: int) -> bool:
        return (cols_mask >> j) & 1

    set_row(start[0])
    set_col(start[1])

    jumps = 1

    while queue:
        for _ in range(len(queue)):
            r, c = queue.popleft()

            for row in range(n):
                if not is_row_set(row) and not board[row][c]:
                    new_cell = (row, c)
                    if two_jump_gap(board, new_cell, end):
                        return jumps + 2
                    set_row(row)
                    queue.append(new_cell)

            for col in range(m):
                if not is_col_set(col) and not board[r][col]:
                    new_cell = (r, col)
                    if two_jump_gap(board, new_cell, end):
                        return jumps + 2
                    set_col(col)
                    queue.append(new_cell)

        jumps += 1

    return -1


def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    q = int(next(it))

    board = []
    for _ in range(n):
        line = list(next(it).strip())
        board.append([ch == '*' for ch in line])

    tests = []
    for _ in range(q):
        y1 = int(next(it)) - 1
        x1 = int(next(it)) - 1
        y2 = int(next(it)) - 1
        x2 = int(next(it)) - 1
        tests.append((y1, x1, y2, x2))

    for y1, x1, y2, x2 in tests:
        res = breadth_first(board, (y1, x1), (y2, x2), n, m)
        print(res)


if __name__ == "__main__":
    main()

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Group: 5

Verdict: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: ACCEPTED

Test 27

Group: 5

Verdict: ACCEPTED