Hypyt

from collections import defaultdict, deque

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.p[y] = x

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

# Kaikki turvalliset solmut
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)
dsu = DSU(num_cells)

# Yhdistä rivin solmut
for i in range(n):
    row = [pos_to_idx[(i,j)] for j in range(m) if grid[i][j] == '.']
    for k in range(1, len(row)):
        dsu.union(row[k-1], row[k])

# Yhdistä sarakkeen solmut
for j in range(m):
    col = [pos_to_idx[(i,j)] for i in range(n) if grid[i][j] == '.']
    for k in range(1, len(col)):
        dsu.union(col[k-1], col[k])

# Luo graafi komponentin sisällä 0-1 BFS:lle
# Käytetään super-solmuja riville ja sarakkeelle (kuten aiemmin)
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
graph = [[] for _ in range(total_nodes)]
for idx, (i,j) in enumerate(safe_cells):
    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))

# Esikäsittele kaikki komponentit: pienin hyppyjen määrä yhdestä solmusta kaikkiin sen komponentin solmuihin
# tallennetaan vain ne solmut, joita kysytään
queries = []
query_positions = set()
for _ in range(q):
    y1,x1,y2,x2 = map(int,input().split())
    y1 -= 1; x1 -= 1; y2 -= 1; x2 -= 1
    queries.append(((y1,x1),(y2,x2)))
    query_positions.add((y1,x1))
    query_positions.add((y2,x2))

# Lasketaan etäisyydet 0-1 BFS:llä vain kyselysolmista
distances = {}
for (y,x) in query_positions:
    start = pos_to_idx[(y,x)]
    d = [float('inf')]*total_nodes
    d[start] = 0
    dq = deque([start])
    while dq:
        u = dq.popleft()
        for v,w in graph[u]:
            if d[v] > d[u]+w:
                d[v] = d[u]+w
                if w==0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    distances[(y,x)] = d

# Vastaukset kyselyihin
for (y1,x1),(y2,x2) in queries:
    idx1 = pos_to_idx[(y1,x1)]
    idx2 = pos_to_idx[(y2,x2)]
    if dsu.find(idx1) != dsu.find(idx2):
        print(-1)
    else:
        ans = distances[(y1,x1)][idx2]
        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