Hypyt

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

rows = [[] for _ in range(n + 1)]
cols = [[] for _ in range(m + 1)]
idx, R, C = {}, [], []

for r in range(1, n + 1):
    s = g[r - 1]
    for c, ch in enumerate(s, 1):
        if ch == '.':
            idx[(r, c)] = len(R)
            R.append(r); C.append(c)
            rows[r].append(c)
            cols[c].append(r)

def dist(y1, x1, y2, x2):
    s, t = idx[(y1, x1)], idx[(y2, x2)]
    if s == t: return 0
    vis = {s: 0}
    usedR, usedC = set(), set()
    q, h = [s], 0
    while h < len(q):
        u = q[h]; h += 1
        d, r, c = vis[u], R[u], C[u]
        if r not in usedR:
            usedR.add(r)
            for cc in rows[r]:
                v = idx[(r, cc)]
                if v not in vis:
                    vis[v] = d + 1
                    if v == t: return d + 1
                    q.append(v)
        if c not in usedC:
            usedC.add(c)
            for rr in cols[c]:
                v = idx[(rr, c)]
                if v not in vis:
                    vis[v] = d + 1
                    if v == t: return d + 1
                    q.append(v)
    return -1

for _ in range(q):
    y1, x1, y2, x2 = map(int, input().split())
    print(dist(y1, x1, y2, x2))

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