Hypyt

from collections import deque

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

def check(k):
    x1, y1, x2, y2 = map(int, k.split())
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1  

    if (x1, y1) == (x2, y2):
        return 0
    if x1 == x2 or y1 == y2:
        return 1

    visited = [[False]*m for _ in range(n)]
    q = deque()
    q.append((x1, y1, 0))
    visited[x1][y1] = True

    while q:
        r, c, steps = q.popleft()

        for j in range(m):
            if rud[r][j] == '.' and not visited[r][j]:
                visited[r][j] = True
                if (r, j) == (x2, y2):
                    return steps + 1
                q.append((r, j, steps + 1))


        for i in range(n):
            if rud[i][c] == '.' and not visited[i][c]:
                visited[i][c] = True
                if (i, c) == (x2, y2):
                    return steps + 1
                q.append((i, c, steps + 1))

    return -1  

for k in kys:
    print(check(k))

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED