Hypyt

import sys
from collections import deque
from array import array

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    n = int(next(it)); m = int(next(it)); q = int(next(it))
    grid = [next(it).decode() for _ in range(n)]

    row_mask = [0] * n
    col_mask = [0] * m
    for r in range(n):
        rm = 0
        row = grid[r]
        for c, ch in enumerate(row):
            if ch == '.':
                rm |= (1 << c)
                col_mask[c] |= (1 << r)
        row_mask[r] = rm

    N = n + m
    INF = 0xFFFF
    dist = [array('H', [INF]) * N for _ in range(N)]
    for s in range(N):
        d = dist[s]
        d[s] = 0
        if s < n:
            Rf = 1 << s
            Cf = 0
        else:
            Rf = 0
            Cf = 1 << (s - n)

        vR, vC = Rf, Cf
        layer = 0

        row_mask_loc = row_mask
        col_mask_loc = col_mask
        bit_len = int.bit_length
        while Rf or Cf:
            layer += 1
            cols_bits = 0
            x = Rf
            while x:
                lb = x & -x
                r = bit_len(lb) - 1
                cols_bits |= row_mask_loc[r]
                x ^= lb
            newC = cols_bits & ~vC
            x = newC
            while x:
                lb = x & -x
                c = bit_len(lb) - 1
                d[n + c] = layer
                x ^= lb
            vC |= newC
            rows_bits = 0
            x = Cf
            while x:
                lb = x & -x
                c = bit_len(lb) - 1
                rows_bits |= col_mask_loc[c]
                x ^= lb
            newR = rows_bits & ~vR
            x = newR
            while x:
                lb = x & -x
                r = bit_len(lb) - 1
                d[r] = layer
                x ^= lb
            vR |= newR
            Rf, Cf = newR, newC
    out_lines = []
    for _ in range(q):
        y1 = int(next(it)) - 1
        x1 = int(next(it)) - 1
        y2 = int(next(it)) - 1
        x2 = int(next(it)) - 1
        if grid[y1][x1] != '.' or grid[y2][x2] != '.':
            out_lines.append("-1")
            continue

        if y1 == y2 and x1 == x2:
            out_lines.append("0")
            continue

        a1, a2 = y1, n + x1
        b1, b2 = y2, n + x2

        dmin = min(dist[a1][b1], dist[a1][b2], dist[a2][b1], dist[a2][b2])
        out_lines.append(str(dmin + 1) if dmin != INF else "-1")

    sys.stdout.write("\n".join(out_lines))


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: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: ACCEPTED

Test 19

Group: 5

Verdict: ACCEPTED

Test 20

Group: 5

Verdict: ACCEPTED

Test 21

Group: 5

Verdict: ACCEPTED

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