Hypyt

import sys
from collections import deque
from array import array


it = iter(sys.stdin.buffer.read().split())
n = int(next(it)); m = int(next(it)); q = int(next(it))
grid = []
for _ in range(n):
    grid.append(next(it).decode())

id_of = [array('i', [-1] * m) for _ in range(n)]
row_cells = [array('I') for _ in range(n)]
col_cells = [array('I') for _ in range(m)]
row_of = array('I')
col_of = array('I')
k = 0
for r in range(n):
    row = grid[r]
    for c in range(m):
        if row[c] == '.':
            id_of[r][c] = k
            row_of.append(r)
            col_of.append(c)
            row_cells[r].append(k)
            col_cells[c].append(k)
            k += 1

if k == 0:
    for _ in range(q):
        print(-1)
    sys.exit(0)
seen_cell = array('I', [0]) * k
seen_row  = array('I', [0]) * n
seen_col  = array('I', [0]) * m
dist = array('I', [0]) * k
token = 0
def bfs(r1, c1, r2, c2):
    global token
    s = id_of[r1][c1]
    t = id_of[r2][c2]
    if s == t:
        return 0
    token += 1
    qd = deque()
    qd.append(s)
    seen_cell[s] = token
    dist[s] = 0
    while qd:
        u = qd.popleft()
        if u == t:
            return dist[u]
        r = row_of[u]
        c = col_of[u]
        if seen_row[r] != token:
            seen_row[r] = token
            for v in row_cells[r]:
                if seen_cell[v] != token:
                    seen_cell[v] = token
                    dist[v] = dist[u] + 1
                    if v == t:
                        return dist[v]
                    qd.append(v)
        if seen_col[c] != token:
            seen_col[c] = token
            for v in col_cells[c]:
                if seen_cell[v] != token:
                    seen_cell[v] = token
                    dist[v] = dist[u] + 1
                    if v == t:
                        return dist[v]
                    qd.append(v)
    return -1
out_lines = []
for _ in range(q):
    r1 = int(next(it)) - 1
    c1 = int(next(it)) - 1
    r2 = int(next(it)) - 1
    c2 = int(next(it)) - 1
    out_lines.append(str(bfs(r1, c1, r2, c2)))
sys.stdout.write("\n".join(out_lines))

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

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