Hypyt

import sys
from collections import deque

def solve():
    try:
        n_str, m_str, q_str = sys.stdin.readline().split()
        n = int(n_str)
        m = int(m_str)
        q = int(q_str)

        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])

            while queue:
                u = queue.popleft()

                for v in adj[u]:

                    if dist[start_node][v] == float('inf'):
                        dist[start_node][v] = dist[start_node][u] + 1
                        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:

        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