Hypyt

import sys

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)
    except EOFError:
        return
    except ValueError:
        return

    grid = [sys.stdin.readline().strip() for _ in range(n)]
    
    V = n + m
    inf = float('inf')
    dist = [[inf] * V for _ in range(V)]

    for i in range(V):
        dist[i][i] = 0

    for r in range(n):
        for c in range(m):
            if grid[r][c] == '.':
                node_r = r
                node_c = c + n
                dist[node_r][node_c] = 1
                dist[node_c][node_r] = 1
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                new_dist = dist[i][k] + dist[k][j]
                if new_dist < dist[i][j]:
                    dist[i][j] = new_dist

    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

        if r1 == r2 or c1 == c2:
            results.append("1")
            continue
        
        node_r1 = r1
        node_c1 = c1 + n
        node_r2 = r2
        node_c2 = c2 + n
        
        ans = min(dist[node_r1][node_r2], dist[node_r1][node_c2], 
                  dist[node_c1][node_r2], dist[node_c1][node_c2])

        if ans == inf:
            results.append("-1")
        else:
            results.append(str(ans + 1))

    sys.stdout.write("\n".join(results) + "\n")

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