Hypyt

from collections import deque, defaultdict
import sys

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

rows = defaultdict(list)
cols = defaultdict(list)


for y in range(n):
    for x, ch in enumerate(rud[y]):
        if ch == '.':
            rows[y].append(x)
            cols[x].append(y)

def bfs(y1, x1, y2, x2):
    if (y1, x1) == (y2, x2):
        return 0

    dq = deque([(y1, x1)])
    dist = {(y1, x1): 0}

    visited_rows = set()
    visited_cols = set()

    while dq:
        y, x = dq.popleft()
        d = dist[(y, x)]

        if y not in visited_rows:
            for nx in rows[y]:
                key = (y, nx)
                if key not in dist:
                    if (y == y2 and nx == x2):
                        return d + 1
                    dist[key] = d + 1
                    dq.append(key)
            visited_rows.add(y)

        if x not in visited_cols:
            for ny in cols[x]:
                key = (ny, x)
                if key not in dist:
                    if (ny == y2 and x == x2):
                        return d + 1
                    dist[key] = d + 1
                    dq.append(key)
            visited_cols.add(x)

    return -1

out = []
for _ in range(q):
    y1, x1, y2, x2 = map(int, input().split())
    out.append(str(bfs(y1-1, x1-1, y2-1, x2-1)))

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

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

Test 25

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED