Hypyt

from collections import deque

n, m, p = map(int, input().split())
grid = []
for i in range(n):
    grid.append(input().strip())

tat = {}
ff = {}
yyy = {}
lll = [] 
pulu = [] 
uuu = []
eee = []
iii = dict()
nums = set()
for i in range(n):
    r = set()
    for j in range(m):
        if grid[i][j] == '.':
            r.add(j)
    lll.append(r)


for i in range(len(lll)):
    for num in lll[i]:
        if num not in tat:
            tat[num] = []
        tat[num].append(i)
        nums.add(num)

for i in range(len(lll)):
    ff[i] = i

sortti = sorted(list(nums))
for i in range(len(sortti)):
    yyy[sortti[i]] = len(lll) + i

ddd = len(ff) + len(yyy)

for i in range(ddd):
    pulu.append([])

for si in range(len(lll)):
    for num in lll[si]:
        ni = yyy[num]
        pulu[si].append(ni)
        pulu[ni].append(si)

for i in range(len(ff) + len(yyy)):
    uuu.append([-1] * ddd)

for src in range(ddd):
    q = deque()
    q.append(src)
    uuu[src][src] = 0
    while len(q)!=0:
        u = q.popleft()
        for v in pulu[u]:
            if uuu[src][v] == -1:
                uuu[src][v] = uuu[src][u] + 1
                q.append(v)

def j(uuu, yyy, a, b, c, d):
    x = min(uuu[a][c],uuu[a][yyy[d]], uuu[yyy[b]][c], uuu[yyy[b]][yyy[d]])
    if x>=0:
        if a!=c or b!=d:
            x+=1
    print(x)

for i in range(p):
    a, b, c, d = map(int, input().split())
    j(uuu, yyy, a-1, b-1, c-1, d-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: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: ACCEPTED

Test 19

Group: 5

Verdict: ACCEPTED

Test 20

Group: 5

Verdict: ACCEPTED

Test 21

Group: 5

Verdict: ACCEPTED

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: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: ACCEPTED

Test 27

Group: 5

Verdict: ACCEPTED