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 = deque(); tQ = deque()
        s_nodes = (r1, n + c1)
        t_nodes = (r2, n + c2)

        for u in s_nodes:
            visS[u] = cur
            distS[u] = 0
            sQ.append(u)
        for u in t_nodes:
            visT[u] = cur
            distT[u] = 0
            tQ.append(u)

        if visS[t_nodes[0]] == cur or visS[t_nodes[1]] == cur:
            out.append("1")
            continue

        found = -1
        while sQ and tQ:
            if len(sQ) <= len(tQ):
                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:
                                found = du + distT[v]
                                sQ.clear(); tQ.clear()
                                break
                            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:
                                found = du + distT[v]
                                sQ.clear(); tQ.clear()
                                break
                            sQ.append(v)
            else:
                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:
                                found = du + distS[v]
                                sQ.clear(); tQ.clear()
                                break
                            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:
                                found = du + distS[v]
                                sQ.clear(); tQ.clear()
                                break
                            tQ.append(v)

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

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

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