Hypyt

from collections import deque



def seatcher():
    n, m, q = map(int, input().split())
    grid = []
    for _ in range(n):
        grid.append(input().strip())
    
    for _ in range(q):
        y1, x1, y2, x2 = map(int, input().split())
        y1 -= 1
        x1 -= 1
        y2 -= 1
        x2 -= 1
        
        if (y1, x1) == (y2, x2):
            print(0)
            continue
        
        queue = deque([(y1, x1, 0)])
        visited = {(y1, x1)}
        found = False
        
        while queue and not found:
            y, x, dist = queue.popleft()
            
            for nx in range(m):
                if grid[y][nx] == '.' and (y, nx) not in visited:
                    if y == y2 and nx == x2:
                        print(dist + 1)
                        found = True
                        break
                    visited.add((y, nx))
                    queue.append((y, nx, dist + 1))
            
            if found:
                break
            
            for ny in range(n):
                if grid[ny][x] == '.' and (ny, x) not in visited:
                    if ny == y2 and x == x2:
                        print(dist + 1)
                        found = True
                        break
                    visited.add((ny, x))
                    queue.append((ny, x, dist + 1))
        
        if not found:
            print(-1)

seatcher()

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