Hypyt

from collections import deque



def searcher():
    n, m, q = map(int, input().split())
    grid = []
    for _ in range(n):
        grid.append(input().strip())
    
    rows = [set() for _ in range(n)]
    cols = [set() for _ in range(m)]
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '.':
                rows[i].add(j)
                cols[j].add(i)
    
    def bfs(start_y, start_x, end_y, end_x):
        if (start_y, start_x) == (end_y, end_x):
            return 0
        
        queue_fwd = deque([(start_y, start_x, 0)])
        queue_bwd = deque([(end_y, end_x, 0)])
        visited_fwd = {(start_y, start_x): 0}
        visited_bwd = {(end_y, end_x): 0}
        explored_rows_fwd = [False] * n
        explored_cols_fwd = [False] * m
        explored_rows_bwd = [False] * n
        explored_cols_bwd = [False] * m
        
        while queue_fwd or queue_bwd:
            if queue_fwd:
                for _ in range(len(queue_fwd)):
                    y, x, dist = queue_fwd.popleft()
                    
                    if not explored_rows_fwd[y]:
                        for nx in list(rows[y]):
                            if (y, nx) in visited_bwd:
                                return dist + 1 + visited_bwd[(y, nx)]
                            if (y, nx) not in visited_fwd:
                                visited_fwd[(y, nx)] = dist + 1
                                queue_fwd.append((y, nx, dist + 1))
                        explored_rows_fwd[y] = True
                    
                    if not explored_cols_fwd[x]:
                        for ny in list(cols[x]):
                            if (ny, x) in visited_bwd:
                                return dist + 1 + visited_bwd[(ny, x)]
                            if (ny, x) not in visited_fwd:
                                visited_fwd[(ny, x)] = dist + 1
                                queue_fwd.append((ny, x, dist + 1))
                        explored_cols_fwd[x] = True
            
            if queue_bwd:
                for _ in range(len(queue_bwd)):
                    y, x, dist = queue_bwd.popleft()
                    
                    if not explored_rows_bwd[y]:
                        for nx in list(rows[y]):
                            if (y, nx) in visited_fwd:
                                return dist + 1 + visited_fwd[(y, nx)]
                            if (y, nx) not in visited_bwd:
                                visited_bwd[(y, nx)] = dist + 1
                                queue_bwd.append((y, nx, dist + 1))
                        explored_rows_bwd[y] = True
                    
                    if not explored_cols_bwd[x]:
                        for ny in list(cols[x]):
                            if (ny, x) in visited_fwd:
                                return dist + 1 + visited_fwd[(ny, x)]
                            if (ny, x) not in visited_bwd:
                                visited_bwd[(ny, x)] = dist + 1
                                queue_bwd.append((ny, x, dist + 1))
                        explored_cols_bwd[x] = True
        
        return -1
    
    for _ in range(q):
        y1, x1, y2, x2 = map(int, input().split())
        print(bfs(y1 - 1, x1 - 1, y2 - 1, x2 - 1))

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