Hypyt

import sys
from collections import deque


class DSU:
    __slots__ = ("p", "sz")
    def __init__(self, n):
        self.p = list(range(n))
        self.sz = [1]*n
    def find(self, x):
        p = self.p
        while p[x] != x:
            p[x] = p[p[x]]
            x = p[x]
        return x
    def union(self, a, b):
        a = self.find(a); b = self.find(b)
        if a == b: return
        if self.sz[a] < self.sz[b]: a, b = b, a
        self.p[b] = a
        self.sz[a] += self.sz[b]


def or_rows_to_cols(rows_mask, row_masks):

    res = 0
    rm = rows_mask
    while rm:
        lb = rm & -rm
        r = lb.bit_length() - 1
        res |= row_masks[r]
        rm ^= lb
    return res

def or_cols_to_rows(cols_mask, col_masks):

    res = 0
    cm = cols_mask
    while cm:
        lb = cm & -cm
        c = lb.bit_length() - 1
        res |= col_masks[c]
        cm ^= lb
    return res


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

    N = n + m
    dsu = DSU(N)


    row_mask = [0]*n
    col_mask = [0]*m

    for r in range(n):
        s = next(it).decode()
        mask = 0
        for c, ch in enumerate(s):
            if ch == '.':
                mask |= 1 << c
                col_mask[c] |= 1 << r
                dsu.union(r, n + c)
        row_mask[r] = mask

    r2r = [None]*n
    c2c = [None]*m

    def ensure_r2r(r):
        if r2r[r] is None:

            res = 0
            rm = row_mask[r]
            while rm:
                lb = rm & -rm
                c = lb.bit_length() - 1
                res |= col_mask[c]
                rm ^= lb
            r2r[r] = res
        return r2r[r]

    def ensure_c2c(c):
        if c2c[c] is None:
            res = 0
            cm = col_mask[c]
            while cm:
                lb = cm & -cm
                r = lb.bit_length() - 1
                res |= row_mask[r]
                cm ^= lb
            c2c[c] = res
        return c2c[c]

    def unreachable(r1, c1, r2, c2):
        a = dsu.find(r1); b = dsu.find(n + c1)
        x = dsu.find(r2); y = dsu.find(n + c2)
        return not (a == x or a == y or b == x or b == y)


    def bidir_bitset_distance(r1, c1, r2, c2):
        RS, CS = (1 << r1), (1 << c1)
        RT, CT = (1 << r2), (1 << c2)

        vRS, vCS = RS, CS
        vRT, vCT = RT, CT
        dS = dT = 0

        while (RS or CS) and (RT or CT):

            if (RS.bit_count() + CS.bit_count()) <= (RT.bit_count() + CT.bit_count()):

                newC = or_rows_to_cols(RS, row_mask) & ~vCS
                newR = or_cols_to_rows(CS, col_mask) & ~vRS

                if (newR & vRT) or (newC & vCT):
                    return dS + 1 + dT

                vRS |= newR; vCS |= newC
                RS, CS = newR, newC
                dS += 1
            else:

                newC = or_rows_to_cols(RT, row_mask) & ~vCT
                newR = or_cols_to_rows(CT, col_mask) & ~vRT

                if (newR & vRS) or (newC & vCS):
                    return dT + 1 + dS

                vRT |= newR; vCT |= newC
                RT, CT = newR, newC
                dT += 1

        return None

    out = []
    for _ in range(q):
        r1 = int(next(it)) - 1
        c1 = int(next(it)) - 1
        r2 = int(next(it)) - 1
        c2 = int(next(it)) - 1

        if r1 == r2 and c1 == c2:
            out.append("0"); continue

        if r1 == r2 or c1 == c2:
            out.append("1"); continue

        if unreachable(r1, c1, r2, c2):
            out.append("-1"); continue

        if ((row_mask[r1] >> c2) & 1) or ((row_mask[r2] >> c1) & 1):
            out.append("2"); continue

        if (row_mask[r1] & row_mask[r2]) or (col_mask[c1] & col_mask[c2]):
            out.append("3"); continue

        if (ensure_r2r(r1) & col_mask[c2]) or (ensure_c2c(c1) & row_mask[r2]):
            out.append("4"); continue
        dist_edges = bidir_bitset_distance(r1, c1, r2, c2)
        out.append(str(dist_edges + 1) if dist_edges is not None else "-1")

    sys.stdout.write("\n".join(out))

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

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

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

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: ACCEPTED

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: ACCEPTED

Test 27

Group: 5

Verdict: ACCEPTED