Hypyt

import sys
from collections import deque

def solve():
    try:
        n, m, q = map(int, sys.stdin.readline().split())
        
        grid = [sys.stdin.readline().strip() for _ in range(n)]
        
        num_nodes = n + m
        adj = [[] for _ in range(num_nodes)]
        
        for r in range(n):
            for c in range(m):
                if grid[r][c] == '.':
                    u = r
                    v = n + c
                    adj[u].append(v)
                    adj[v].append(u)
                    
        dist = [[float('inf')] * num_nodes for _ in range(num_nodes)]
        
        for start_node in range(num_nodes):
            if not adj[start_node]:
                continue
                
            dist[start_node][start_node] = 0
            queue = deque([start_node])
            
            visited = [False] * num_nodes
            visited[start_node] = True
            
            d_level = [float('inf')] * num_nodes
            d_level[start_node] = 0
            
            queue = deque([start_node])
            
            while queue:
                u = queue.popleft()
                
                for v in adj[u]:
                    if d_level[v] == float('inf'):
                        d_level[v] = d_level[u] + 1
                        dist[start_node][v] = d_level[v]
                        queue.append(v)

        results = []
        for _ in range(q):
            y1, x1, y2, x2 = map(int, sys.stdin.readline().split())
            
            r1, c1 = y1 - 1, x1 - 1
            r2, c2 = y2 - 1, x2 - 1
            
            if r1 == r2 and c1 == c2:
                results.append("0")
                continue
                
            u1, v1 = r1, n + c1
            u2, v2 = r2, n + c2
            
            d_r = min(dist[u1][u2], dist[v1][u2])
            
            d_c = min(dist[u1][v2], dist[v1][v2])

            ans = float('inf')

            if d_r != float('inf'):
                ans = min(ans, d_r + 1)
            if d_c != float('inf'):
                ans = min(ans, d_c + 1)
            if d_c == d_r + 1:
                ans = min(ans, d_c)
            if d_r == d_c + 1:
                ans = min(ans, d_r)


            if ans == float('inf'):
                results.append("-1")
            else:
                results.append(str(ans))
                
        sys.stdout.write("\n".join(results) + "\n")

    except EOFError:
        pass
    except Exception as e:
        pass

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

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

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

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