Hypyt

n, m, k = (int(x) for x in input().split())
lis = []
t =True
while t:
    if n==1:
        t= False
    n=n-1
    a = input()
    lis.append(a)

grid = lis

Graph = {}

rows = len(grid)
cols = len(grid[0])
#poits
dots = [(e, c) for e in range(rows) for c in range(cols) if grid[e][c] == '.']
#print(dots)

for e, c in dots:
    Graph[f"{e},{c}"] = []
#print(Graph)

for (e1, c1) in dots:
    for (e2, c2) in dots:

        if (e1, c1) != (e2, c2):
            if e1 == e2 or c1 == c2:  
                Graph[f"{e1},{c1}"].append(f"{e2},{c2}")

#print("Graph =", Graph)


def short_path(graph, start, end):
    
    queue = [[start]]
    visited = set()

    while queue:
        path = queue.pop(0)
        node = path[-1]

        if node == end:
            return len(path)-1

        if node not in visited:
            visited.add(node)
            for eig in graph[node]:
                n_p = list(path)
                n_p.append(eig)
                queue.append(n_p)
    return -1
t= True
pr= []
for b in range(0,k):
    n1, m2, k3, k4 = (int(x) for x in input().split())
    n1 -=1
    m2 -=1
    k3 -=1
    k4 -=1
    h= str(n1)+","+str(m2)
    g= str(k3)+","+str(k4)
    #print(h,g)
    pr.append(short_path(Graph, h, g))
for o in pr:
    print(o)

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