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(x)
            cols[x].append(y)

adj = [[[] for _ in range(m)] for _ in range(n)]

for y in range(n):
    xs = rows[y]
    if not xs:
        continue
    if len(xs) == 1:
        continue
    for i, x in enumerate(xs):
        row_neighbors = []
        for j, nx in enumerate(xs):
            if nx == x:
                continue
            row_neighbors.append((y, nx))
        adj[y][x].extend(row_neighbors)

for x in range(m):
    ys = cols[x]
    if not ys:
        continue
    if len(ys) == 1:
        continue
    for i, y in enumerate(ys):
        col_neighbors = []
        for j, ny in enumerate(ys):
            if ny == y:
                continue
            col_neighbors.append((ny, x))
        adj[y][x].extend(col_neighbors)

dist = [[-1] * m for _ in range(n)]
visited = [[0] * m for _ in range(n)]
current_gen = 0 

def bfs(start, target):  
    global current_gen
    current_gen += 1

    sy, sx = start
    ty, tx = target

    dq = deque()
    dq.append((sy, sx))
    dist[sy][sx] = 0
    visited[sy][sx] = current_gen


    while dq:
        y, x = dq.popleft()
        d = dist[y][x]
        if (y, x) == (ty, tx):
            return d
        
        for ny, nx in adj[y][x]:
            if visited[ny][nx] != current_gen:
                visited[ny][nx] = current_gen
                dist[ny][nx] = d + 1
                dq.append((ny, nx))

    return -1

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

    if (y1 - 1, x1 - 1) == (y2 - 1, x2 - 1):
        print(0)
    else:
        print(bfs((y1 - 1, x1 - 1), (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: 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: 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