Hypyt

import sys
from collections import deque


class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.sz = [1]*n
    def find(self, x):
        p = self.p
        while p[x] != x:
            p[x] = p[p[x]]
            x = p[x]
        return x
    def union(self, a, b):
        a = self.find(a); b = self.find(b)
        if a == b: return
        if self.sz[a] < self.sz[b]: a, b = b, a
        self.p[b] = a
        self.sz[a] += self.sz[b]


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

    rows = [[] for _ in range(n)]
    cols = [[] for _ in range(m)]

    for r in range(n):
        s = next(it).decode()
        for c, ch in enumerate(s):
            if ch == '.':
                rows[r].append(c)
                cols[c].append(r)

    N = n + m

    dsu = DSU(N)
    for r in range(n):
        for c in rows[r]:
            dsu.union(r, n + c)
    vis = [0] * N
    dist = [0] * N
    cur = 0

    def bfs_two(start, t1, t2, lim):
        nonlocal cur
        cur += 1
        vmark, darr = vis, dist
        dq = deque([start])
        vmark[start] = cur
        darr[start] = 0

        INF = 10**9
        best1 = 0 if start == t1 else INF
        best2 = 0 if start == t2 else INF
        nloc = n
        rowsl, colsl = rows, cols

        while dq:
            u = dq.popleft()
            du = darr[u] + 1
            if du > lim:
                continue

            if u < nloc:
                for c in rowsl[u]:
                    v = nloc + c
                    if vmark[v] != cur:
                        vmark[v] = cur
                        darr[v] = du
                        dq.append(v)
                        if v == t1:
                            if du < best1: best1 = du; lim = min(lim, du)
                        elif v == t2:
                            if du < best2: best2 = du; lim = min(lim, du)
            else:
                c = u - nloc
                for r in colsl[c]:
                    v = r
                    if vmark[v] != cur:
                        vmark[v] = cur
                        darr[v] = du
                        dq.append(v)
                        if v == t1:
                            if du < best1: best1 = du; lim = min(lim, du)
                        elif v == t2:
                            if du < best2: best2 = du; lim = min(lim, du)

        return best1, best2
    out = []
    INF = 10**9
    for _ in range(q):
        r1 = int(next(it)) - 1
        c1 = int(next(it)) - 1
        r2 = int(next(it)) - 1
        c2 = int(next(it)) - 1
        if r1 == r2 and c1 == c2:
            out.append("0"); continue
        if r1 == r2 or c1 == c2:
            out.append("1"); continue

        a, b = dsu.find(r1), dsu.find(n + c1)
        x, y = dsu.find(r2), dsu.find(n + c2)
        if not (a == x or a == y or b == x or b == y):
            out.append("-1"); continue

        tR, tC = r2, n + c2

        degR = len(rows[r1])
        degC = len(cols[c1])

        if degR <= degC:
            d1, d2 = bfs_two(r1, tR, tC, INF)
            lim = min(d1, d2)
            e1, e2 = bfs_two(n + c1, tR, tC, lim - 1 if lim < INF else INF)
        else:
            d1, d2 = bfs_two(n + c1, tR, tC, INF)
            lim = min(d1, d2)
            e1, e2 = bfs_two(r1, tR, tC, lim - 1 if lim < INF else INF)

        best = min(d1, d2, e1, e2)
        out.append("-1" if best >= INF else str(best + 1))

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


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: TIME LIMIT EXCEEDED

Test 10

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED