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))
    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
    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 r1 == r2 and c1 == c2:
            out.append("0")
            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