Hypyt

from collections import deque, defaultdict

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

# Luo solmut: jokainen turvallinen ruutu ja rivin/sarakkeen super-solmu
safe_cells = []
pos_to_idx = {}
idx = 0

for i in range(n):
    for j in range(m):
        if grid[i][j] == '.':
            pos_to_idx[(i,j)] = idx
            safe_cells.append((i,j))
            idx += 1

num_cells = len(safe_cells)
# Rivin ja sarakkeen super-solmut
row_nodes = [num_cells + i for i in range(n)]
col_nodes = [num_cells + n + j for j in range(m)]
total_nodes = num_cells + n + m

# Luo graafi (0-1 BFS)
graph = [[] for _ in range(total_nodes)]

for idx, (i,j) in enumerate(safe_cells):
    # liitä solmu rivin ja sarakesolmuun (0-kustannus)
    graph[idx].append((row_nodes[i], 0))
    graph[idx].append((col_nodes[j], 0))
    graph[row_nodes[i]].append((idx,1))
    graph[col_nodes[j]].append((idx,1))

# Funktio: 0-1 BFS yhdestä lähteestä
def zero_one_bfs(start):
    dist = [float('inf')]*total_nodes
    dist[start] = 0
    dq = deque([start])
    while dq:
        u = dq.popleft()
        for v, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

# Käsitellään kyselyt
for _ in range(q):
    y1, x1, y2, x2 = map(int, input().split())
    y1 -= 1; x1 -= 1; y2 -= 1; x2 -= 1
    src = pos_to_idx[(y1,x1)]
    dst = pos_to_idx[(y2,x2)]
    dist = zero_one_bfs(src)
    ans = dist[dst]
    print(ans if ans != float('inf') else -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: TIME LIMIT EXCEEDED