Hypyt

from collections import deque, defaultdict

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 in range(m):
        if rud[y][x] == '.':
            rows[y].append(x)
            cols[x].append(y)

def bfs(y1, x1, y2, x2):
    if (y1, x1) == (y2, x2):
        return 0
    dist = {(y1, x1): 0}
    dq = deque([(y1, x1)])
    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]:
                if (y, nx) not in dist:
                    dist[(y, nx)] = d + 1
                    dq.append((y, nx))
            visited_rows.add(y)
        
        if x not in visited_cols:
            for ny in cols[x]:
                if (ny, x) not in dist:
                    dist[(ny, x)] = d + 1
                    dq.append((ny, x))
            visited_cols.add(x)
        
        if (y2, x2) in dist:
            return dist[(y2, x2)]
    
    return -1

l = []
for _ in range(q):
    y1, x1, y2, x2 = map(lambda z: int(z)-1, input().split())
    l.append(f"{str(bfs(y1, x1, y2, x2))}\n")

print("".join(l))

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