Hypyt

from collections import deque

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

rows = [[] for _ in range(n)]
cols = [[] for _ in range(m)]

for y in range(n):
    for x in range(m):
        if grid[y][x] == '.':
            rows[y].append((y, x))
            cols[x].append((y, x))

# Cache distance map. If start position is the same then use cached map.
bfs_cache = {}

def bfs(start):

    if start in bfs_cache:
        return bfs_cache[start]
    
    sy, sx = start
    dist = [[-1] * m for _ in range(n)]
    dq = deque([(sy, sx)])
    dist[sy][sx] = 0
    used_rows = [False] * n
    used_cols = [False] * m

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

        # Expand all points in this row
        if not used_rows[y]:
            for ny, nx in rows[y]:
                if dist[ny][nx] == -1:
                    dist[ny][nx] = d + 1
                    dq.append((ny, nx))
            used_rows[y] = True

        # Expand all points in this column
        if not used_cols[x]:
            for ny, nx in cols[x]:
                if dist[ny][nx] == -1:
                    dist[ny][nx] = d + 1
                    dq.append((ny, nx))
            used_cols[x] = True

    bfs_cache[start] = dist
    return dist

for _ in range(q):
    y1, x1, y2, x2 = map(int, input().split()) 

    if (y1 - 1, x1 - 1) == (y2 - 1, x2 - 1):
        print(0)
    else:
        dist_map = bfs((y1 - 1, x1 - 1))
        print(dist_map[y2 - 1][x2 - 1])

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: 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: 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: RUNTIME ERROR

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

Test 27

Group: 5

Verdict: ACCEPTED