Hypyt

import copy

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)
row = {}
col = {}
n = len(lis)
for i in range(n):
    for j in range(m):
        if lis[i][j] == ".":
            if i not in row:
                row[i] = []
            row[i].append(j)
            if j not in col:
                col[j] = []
            col[j].append(i)
row = {}
col = {}
n = len(lis)
for i in range(n):
    for j in range(m):
        if lis[i][j] == ".":
            if i not in row:
                row[i] = []
            row[i].append(j)
            if j not in col:
                col[j] = []
            col[j].append(i)

yt = []
def s_p(s, d):
    sx, sy = s
    dx, dy = d
    rows = copy.copy(row)
    cols = copy.copy(col)
    
    q = [(sx, sy, 0)]
    v = {(sx, sy)}

    f = 0  

    while f < len(q):
        z, w, dist = q[f]
        f += 1

        if (z, w) == (dx, dy):
            return dist       
        if z in rows:
            for c1 in rows[z]:
                if (z, c1) not in v:
                    v.add((z,c1))
                    q.append((z, c1,dist+ 1))
            rows[z] = []  
        if w in cols:
            for r4 in cols[w]:
                if (r4, w) not in v:
                    v.add((r4, w))
                    q.append((r4,w, dist + 1))
            cols[w] = [] 

    return -1
pr= []
al =[]
for b in range(0,k):
    n1, m2, k3, k4 = (int(x) for x in input().split())
    h= (n1-1, m2-1)
    g= (k3-1, k4-1)
    t = s_p(h, g)
    b = s_p(g, h)
    pr.append(t)

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