Hypyt

import sys
from collections import deque
from array import array


def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it)); m = int(next(it)); q = int(next(it))

    rows = [[] for _ in range(n)]
    cols = [[] for _ in range(m)]
    grid = []
    for r in range(n):
        s = next(it)
        grid.append(s)
        for c, ch in enumerate(s):
            if ch == '.':
                rows[r].append(c)
                cols[c].append(r)

    row_mark = array('I', [0]) * n
    col_mark = array('I', [0]) * m
    cell_mark = array('I', [0]) * (n * m)
    cur = 0  # текущая версия

    out_lines = []
    for _ in range(q):
        y1 = int(next(it)) - 1
        x1 = int(next(it)) - 1
        y2 = int(next(it)) - 1
        x2 = int(next(it)) - 1
        s = y1 * m + x1
        t = y2 * m + x2

        if s == t:
            out_lines.append("0")
            continue

        cur += 1
        dq = deque([s])
        cell_mark[s] = cur
        found = False
        dist = 0

        while dq and not found:
            for _ in range(len(dq)):
                v = dq.popleft()
                if v == t:
                    out_lines.append(str(dist))
                    found = True
                    break
                r = v // m
                c = v % m

                if row_mark[r] != cur:
                    row_mark[r] = cur
                    base = r * m
                    for cc in rows[r]:
                        nid = base + cc
                        if cell_mark[nid] != cur:
                            cell_mark[nid] = cur
                            dq.append(nid)

                if col_mark[c] != cur:
                    col_mark[c] = cur
                    for rr in cols[c]:
                        nid = rr * m + c
                        if cell_mark[nid] != cur:
                            cell_mark[nid] = cur
                            dq.append(nid)
            if not found:
                dist += 1

        if not found:
            out_lines.append("-1")

    print("\n".join(out_lines))


if __name__ == "__main__":
    main()

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