Hypyt

import sys
from collections import deque



def searcher():
    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)]
    rows = [set() for _ in range(n)]
    cols = [set() for _ in range(m)]
    
    for i in range(n):
        row = grid[i]
        for j, ch in enumerate(row):
            if ch == '.':
                rows[i].add(j)
                cols[j].add(i)

    V = n + m
    base = n
    adj = [[] for _ in range(V)]
    
    for i in range(n):
        u = i
        for j in rows[i]:
            v = base + j
            adj[u].append(v)
            adj[v].append(u)

    dist = [[-1] * V for _ in range(V)]
    
    for s in range(V):
        d = dist[s]
        d[s] = 0
        dq = deque([s])
        pop = dq.popleft; app = dq.append
        while dq:
            u = pop()
            du = d[u] + 1
            for v in adj[u]:
                if d[v] == -1:
                    d[v] = du
                    app(v)

    out = []
    INF = 10**9
    
    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

        u1 = y1
        v1 = base + x1
        u2 = y2
        v2 = base + x2

        best = INF
        d = dist[u1][u2]
        if d != -1 and d < best: best = d
        d = dist[v1][v2]
        if d != -1 and d < best: best = d
        d = dist[u1][v2]
        if d != -1 and d < best: best = d
        d = dist[v1][u2]
        if d != -1 and d < best: best = d

        out.append(str(best + 1 if best != INF else -1))

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


searcher()

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: 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: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

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: ACCEPTED

Test 27

Group: 5

Verdict: ACCEPTED