Hypyt

from collections import deque

def solve():
    n, m, q = map(int, input().split())
    grid = []
    for _ in range(n):
        grid.append(input().strip())
    
    safe_rows = [[] for _ in range(n)]
    safe_cols = [[] for _ in range(m)]
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '.':
                safe_rows[i].append(j)
                safe_cols[j].append(i)
    
    def bfs(start_y, start_x, end_y, end_x):
        if start_y == end_y and start_x == end_x:
            return 0
        
        visited = set()
        queue = deque([(start_y, start_x, 0)])
        visited.add((start_y, start_x))
        
        while queue:
            y, x, dist = queue.popleft()
            
            for next_x in safe_rows[y]:
                if next_x != x and (y, next_x) not in visited:
                    if y == end_y and next_x == end_x:
                        return dist + 1
                    visited.add((y, next_x))
                    queue.append((y, next_x, dist + 1))
            
            for next_y in safe_cols[x]:
                if next_y != y and (next_y, x) not in visited:
                    if next_y == end_y and x == end_x:
                        return dist + 1
                    visited.add((next_y, x))
                    queue.append((next_y, x, dist + 1))
        
        return -1
    
    for _ in range(q):
        y1, x1, y2, x2 = map(int, input().split())
        y1 -= 1
        x1 -= 1
        y2 -= 1
        x2 -= 1
        print(bfs(y1, x1, y2, x2))

solve()

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