Hypyt

from collections import deque



def searcher():
    n, m, q = map(int, input().split())
    grid = []
    for _ in range(n):
        grid.append(input().strip())
    
    rows = [[] for _ in range(n)]
    cols = [[] for _ in range(m)]
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '.':
                rows[i].append(j)
                cols[j].append(i)
    
    
    def fast_searcher(sy, sx, ey, ex):
        if (sy, sx) == (ey, ex):
            return 0
        
        queue = deque([(sy, sx)])
        dist = {(sy, sx): 0}
        used_rows = [False] * n
        used_cols = [False] * m
        
        while queue:
            y, x = queue.popleft()
            d = dist[(y, x)]
            
            if not used_rows[y]:
                used_rows[y] = True
                for nx in rows[y]:
                    if (y, nx) not in dist:
                        dist[(y, nx)] = d + 1
                        if y == ey and nx == ex:
                            return d + 1
                        queue.append((y, nx))
            
            if not used_cols[x]:
                used_cols[x] = True
                for ny in cols[x]:
                    if (ny, x) not in dist:
                        dist[(ny, x)] = d + 1
                        if ny == ey and x == ex:
                            return d + 1
                        queue.append((ny, x))
        
        return -1
    
    cache = {}
    
    for _ in range(q):
        y1, x1, y2, x2 = map(int, input().split())
        y1 -= 1
        x1 -= 1
        y2 -= 1
        x2 -= 1
        
        if grid[y1][x1] != '.' or grid[y2][x2] != '.':
            print(-1)
            continue
        
        query = (y1, x1, y2, x2)
        
        if query not in cache:
            cache[query] = fast_searcher(y1, x1, y2, x2)   
            
        print(cache[query])

searcher()

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: 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: 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: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED