Hypyt

import sys
from collections import deque
from array import array


class DSU:
    __slots__ = ("p", "sz")
    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)]
    grid = [None]*n

    for r in range(n):
        s = next(it).decode()
        grid[r] = s
        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):
        base_r = r
        for c in rows[r]:
            dsu.union(base_r, n + c)

    visS = array('I', [0]) * N
    visT = array('I', [0]) * N
    distS = array('I', [0]) * N
    distT = array('I', [0]) * N
    cur = 0

    out = []
    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 grid[r1][c1] != '.' or grid[r2][c2] != '.':
            out.append("-1")
            continue

        if r1 == r2 and c1 == c2:
            out.append("0")
            continue

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

        cur += 1
        sQ, tQ = deque(), deque()

        for u in (r1, n + c1):
            visS[u] = cur
            distS[u] = 0
            sQ.append(u)
        for u in (r2, n + c2):
            visT[u] = cur
            distT[u] = 0
            tQ.append(u)

        if visS[r2] == cur or visS[n + c2] == cur:
            out.append("1")
            continue

        found = -1
        while sQ and tQ:
            if len(sQ) <= len(tQ):
                size = len(sQ)
                best = None
                for _ in range(size):
                    u = sQ.popleft()
                    du = distS[u] + 1
                    if u < n:
                        for c in rows[u]:
                            v = n + c
                            if visS[v] != cur:
                                visS[v] = cur
                                distS[v] = du
                                if visT[v] == cur:
                                    cand = du + distT[v]
                                    best = cand if best is None else min(best, cand)
                                else:
                                    sQ.append(v)
                    else:
                        c = u - n
                        for r in cols[c]:
                            v = r
                            if visS[v] != cur:
                                visS[v] = cur
                                distS[v] = du
                                if visT[v] == cur:
                                    cand = du + distT[v]
                                    best = cand if best is None else min(best, cand)
                                else:
                                    sQ.append(v)
                if best is not None:
                    found = best
                    break
            else:
                size = len(tQ)
                best = None
                for _ in range(size):
                    u = tQ.popleft()
                    du = distT[u] + 1
                    if u < n:
                        for c in rows[u]:
                            v = n + c
                            if visT[v] != cur:
                                visT[v] = cur
                                distT[v] = du
                                if visS[v] == cur:
                                    cand = du + distS[v]
                                    best = cand if best is None else min(best, cand)
                                else:
                                    tQ.append(v)
                    else:
                        c = u - n
                        for r in cols[c]:
                            v = r
                            if visT[v] != cur:
                                visT[v] = cur
                                distT[v] = du
                                if visS[v] == cur:
                                    cand = du + distS[v]
                                    best = cand if best is None else min(best, cand)
                                else:
                                    tQ.append(v)
                if best is not None:
                    found = best
                    break

        out.append(str(found + 1) if found != -1 else "-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