Hypyt

n, m, q = map(int, input().split())


grid = [input().strip() for _ in range(n)]


queries = [tuple(map(int, input().split())) for _ in range(q)]
 



r_safespaces = [[] for _ in range(n + 1)]
c_safespaces = [[] for _ in range(m + 1)]
for r in range(1, n+1):
    row = grid[r-1]
    for c in range(1, m+1):
        if row[c-1] == ".":
            r_safespaces[r].append(c)
            c_safespaces[c].append(r)

def jump(y1, x1, y2, x2):
    if x1 == x2 and y1 == y2:
        return 0
    queue = []
    visited = set()
    queue.append(("r", y1, 0))
    queue.append(("c", x1, 0))
    visited.add(("r", y1))
    visited.add(("c", x1))
    while queue:
        tipe, id, distance = queue.pop(0)
        if tipe == "r":
            if id == y2 and x2 in r_safespaces[id]:
                return distance+1
            for c in r_safespaces[id]:
                if ("c", c) not in visited:
                    visited.add(("c", c))
                    queue.append(("c", c, distance+1))
        else:
            if id == x2 and y2 in c_safespaces[id]:  
                return distance+1
            for r in c_safespaces[id]:
                if ("r", r) not in visited:
                    visited.add(("r", r))
                    queue.append(("r", r, distance+1))
    return -1
for query in queries:
    y1, x1, y2, x2 = query
    print(jump(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: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED