Hypyt

import sys
from collections import deque, defaultdict

input = sys.stdin.readline
write = sys.stdout.write

n, m, q = map(int, input().split())
rud = [input().strip() for _ in range(n)]

graph = [[] for _ in range(n + m)]

for y in range(n):
    for x, ch in enumerate(rud[y]):
        if ch == '.':
            ry = y
            cx = n + x
            graph[ry].append(cx)
            graph[cx].append(ry)

comp = [-1] * (n + m)
comp_id = 0

for start in range(n + m):
    if comp[start] != -1:
        continue
    dq = deque([start])
    comp[start] = comp_id
    while dq:
        u = dq.popleft()
        for v in graph[u]:
            if comp[v] == -1:
                comp[v] = comp_id
                dq.append(v)
    comp_id += 1

def bfs_dist(y1, x1, y2, x2):

    start_r, start_c = y1, n + x1
    end_r, end_c = y2, n + x2
    if comp[start_r] != comp[end_r]:
        return -1
    if (y1, x1) == (y2, x2):
        return 0


    dq1 = deque([start_r, start_c])
    dq2 = deque([end_r, end_c])
    dist1 = {start_r: 0, start_c: 1}
    dist2 = {end_r: 0, end_c: 1}

    while dq1 and dq2:
        if len(dq1) <= len(dq2):
            dq = dq1
            dist_a, dist_b = dist1, dist2
        else:
            dq = dq2
            dist_a, dist_b = dist2, dist1

        for _ in range(len(dq)):
            u = dq.popleft()
            d = dist_a[u]
            for v in graph[u]:
                if v in dist_b:
                    return (d + dist_b[v]) // 2
                if v not in dist_a:
                    dist_a[v] = d + 1
                    dq.append(v)
    return -1

out = []
for _ in range(q):
    y1, x1, y2, x2 = map(lambda z: int(z) - 1, input().split())
    if rud[y1][x1] != '.' or rud[y2][x2] != '.':
        out.append("-1")
    else:
        out.append(str(bfs_dist(y1, x1, y2, x2)))

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

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 10

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: WRONG ANSWER

Test 13

Group: 4, 5

Verdict: WRONG ANSWER

Test 14

Group: 4, 5

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 23

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 24

Group: 5

Verdict: WRONG ANSWER

Test 25

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED