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)]

    N = n + m
    adj = [[] for _ in range(N)]
    for r in range(n):
        for c, ch in enumerate(grid[r]):
            if ch == '.':
                u, v = r, n + c
                adj[u].append(v)
                adj[v].append(u)

    INF = 65535
    dist = [array('H', [INF]) * N for _ in range(N)]
    for s in range(N):
        d = dist[s]
        dq = deque([s])
        d[s] = 0
        while dq:
            x = dq.popleft()
            nx = d[x] + 1
            for y in adj[x]:
                if d[y] == INF:
                    d[y] = nx
                    dq.append(y)
    out = []
    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 y1 == y2 and x1 == x2:
            out.append("0")
            continue
        r1, c1 = y1, n + x1
        r2, c2 = y2, n + x2

        dmin = min(
            dist[r1][r2], dist[r1][c2],
            dist[c1][r2], dist[c1][c2]
        )

        if dmin == INF:
            out.append("-1")
        else:
            out.append(str(dmin + 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: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

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

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

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

Test 27

Group: 5

Verdict: ACCEPTED