Hypyt

import sys
from collections import deque
from array import array


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 make_sets_for_heavy(adj_lists, heavy_deg):
    n = len(adj_lists)
    has_set = [False]*n
    sets = [None]*n
    for i, lst in enumerate(adj_lists):
        if len(lst) >= heavy_deg:
            s = set(lst)
            sets[i] = s
            has_set[i] = True
    return sets, has_set

@staticmethod
def _contains_in_list(lst, x):
    for v in lst:
        if v == x:
            return True
    return False

def in_row(rows, row_sets, row_has_set, r, c):
    return (c in row_sets[r]) if row_has_set[r] else _contains_in_list(rows[r], c)

def in_col(cols, col_sets, col_has_set, c, r):
    return (r in col_sets[c]) if col_has_set[c] else _contains_in_list(cols[c], r)

def rows_share_col(rows, row_sets, row_has_set, r1, r2):
    if row_has_set[r1] and row_has_set[r2]:
        a, b = (r1, r2) if len(row_sets[r1]) < len(row_sets[r2]) else (r2, r1)
        sA, sB = row_sets[a], row_sets[b]
        for x in sA:
            if x in sB:
                return True
        return False
    A, B = (r1, r2) if len(rows[r1]) < len(rows[r2]) else (r2, r1)
    if row_has_set[B]:
        sB = row_sets[B]
        for x in rows[A]:
            if x in sB:
                return True
        return False
    else:
        lstB = rows[B]
        for x in rows[A]:
            for y in lstB:
                if x == y:
                    return True
        return False

def cols_share_row(cols, col_sets, col_has_set, c1, c2):
    if col_has_set[c1] and col_has_set[c2]:
        a, b = (c1, c2) if len(col_sets[c1]) < len(col_sets[c2]) else (c2, c1)
        sA, sB = col_sets[a], col_sets[b]
        for x in sA:
            if x in sB:
                return True
        return False
    A, B = (c1, c2) if len(cols[c1]) < len(cols[c2]) else (c2, c1)
    if col_has_set[B]:
        sB = col_sets[B]
        for x in cols[A]:
            if x in sB:
                return True
        return False
    else:
        lstB = cols[B]
        for x in cols[A]:
            for y in lstB:
                if x == y:
                    return True
        return False

def has_len4_via_rows(rows, cols, row_sets, row_has_set, col_sets, col_has_set, r1, c2):
    if not rows[r1]:
        return False
    deg_c2 = len(col_sets[c2]) if col_has_set[c2] else len(cols[c2])
    if deg_c2 < len(rows[r1]):
        if col_has_set[c2]:
            for r in col_sets[c2]:
                if rows_share_col(rows, row_sets, row_has_set, r1, r):
                    return True
        else:
            for r in cols[c2]:
                if rows_share_col(rows, row_sets, row_has_set, r1, r):
                    return True
        return False
    if col_has_set[c2]:
        s2 = col_sets[c2]
        for c in rows[r1]:
            if col_has_set[c]:
                a, b = (c, c2) if len(col_sets[c]) < len(s2) else (c2, c)
                sA, sB = (col_sets[a], col_sets[b])
                for rr in sA:
                    if rr in sB:
                        return True
            else:
                lst = cols[c]
                for rr in lst:
                    if rr in s2:
                        return True
        return False
    else:
        s2_list = cols[c2]
        s2_set = None
        for c in rows[r1]:
            if col_has_set[c]:
                sC = col_sets[c]
                for rr in s2_list:
                    if rr in sC:
                        return True
            else:
                lst = cols[c]
                for rr in lst:
                    for x in s2_list:
                        if rr == x:
                            return True
        return False

def has_len4_via_cols(rows, cols, row_sets, row_has_set, col_sets, col_has_set, c1, r2):
    if not cols[c1]:
        return False
    deg_r2 = len(row_sets[r2]) if row_has_set[r2] else len(rows[r2])
    if deg_r2 < len(cols[c1]):
        if row_has_set[r2]:
            for c in row_sets[r2]:
                if col_has_set[c]:
                    for rr in col_sets[c]:
                        if in_col(cols, col_sets, col_has_set, c1, rr):
                            return True
                else:
                    for rr in cols[c]:
                        if in_col(cols, col_sets, col_has_set, c1, rr):
                            return True
        else:
            for c in rows[r2]:
                if col_has_set[c]:
                    for rr in col_sets[c]:
                        if in_col(cols, col_sets, col_has_set, c1, rr):
                            return True
                else:
                    for rr in cols[c]:
                        if in_col(cols, col_sets, col_has_set, c1, rr):
                            return True
        return False
    if row_has_set[r2]:
        s2 = row_sets[r2]
        for r in cols[c1]:
            if row_has_set[r]:
                a, b = (r, r2) if len(row_sets[r]) < len(s2) else (r2, r)
                sA, sB = (row_sets[a], row_sets[b])
                for cc in sA:
                    if cc in sB:
                        return True
            else:
                for cc in rows[r]:
                    if cc in s2:
                        return True
        return False
    else:
        lst2 = rows[r2]
        for r in cols[c1]:
            if row_has_set[r]:
                sR = row_sets[r]
                for cc in lst2:
                    if cc in sR:
                        return True
            else:
                lst = rows[r]
                for cc in lst:
                    for x in lst2:
                        if cc == x:
                            return True
        return False


def bidir_bfs_rows_cols(n, m, rows, cols, s_nodes, t_nodes):
    N = n + m
    visS = bidir_bfs_rows_cols.visS
    visT = bidir_bfs_rows_cols.visT
    distS = bidir_bfs_rows_cols.distS
    distT = bidir_bfs_rows_cols.distT
    cur = bidir_bfs_rows_cols.cur + 1
    bidir_bfs_rows_cols.cur = cur

    from collections import deque
    sQ, tQ = deque(), deque()

    sumdegS = 0; sumdegT = 0

    for u in s_nodes:
        visS[u] = cur; distS[u] = 0; sQ.append(u)
        sumdegS += (len(rows[u]) if u < n else len(cols[u - n]))
    for u in t_nodes:
        if visS[u] == cur:
            return 0
        visT[u] = cur; distT[u] = 0; tQ.append(u)
        sumdegT += (len(rows[u]) if u < n else len(cols[u - n]))

    for u in t_nodes:
        if visS[u] == cur:
            return 0

    while sQ and tQ:
        expandS = (sumdegS <= sumdegT)
        if expandS:
            size = len(sQ)
            best = None
            for _ in range(size):
                u = sQ.popleft()
                du = distS[u] + 1
                if u < n:
                    nbrs = rows[u]
                    for c in nbrs:
                        v = n + c
                        if visS[v] != cur:
                            visS[v] = cur; distS[v] = du; sQ.append(v)
                            sumdegS += len(cols[c])
                            if visT[v] == cur:
                                cand = du + distT[v]
                                best = cand if best is None else min(best, cand)
                else:
                    c = u - n
                    nbrs = cols[c]
                    for r in nbrs:
                        v = r
                        if visS[v] != cur:
                            visS[v] = cur; distS[v] = du; sQ.append(v)
                            sumdegS += len(rows[r])
                            if visT[v] == cur:
                                cand = du + distT[v]
                                best = cand if best is None else min(best, cand)
            if best is not None:
                return best
        else:
            size = len(tQ)
            best = None
            for _ in range(size):
                u = tQ.pop()
                du = distT[u] + 1
                if u < n:
                    nbrs = rows[u]
                    for c in nbrs:
                        v = n + c
                        if visT[v] != cur:
                            visT[v] = cur; distT[v] = du; tQ.appendleft(v)
                            sumdegT += len(cols[c])
                            if visS[v] == cur:
                                cand = du + distS[v]
                                best = cand if best is None else min(best, cand)
                else:
                    c = u - n
                    nbrs = cols[c]
                    for r in nbrs:
                        v = r
                        if visT[v] != cur:
                            visT[v] = cur; distT[v] = du; tQ.appendleft(v)
                            sumdegT += len(rows[r])
                            if visS[v] == cur:
                                cand = du + distS[v]
                                best = cand if best is None else min(best, cand)
            if best is not None:
                return best

    return -1


bidir_bfs_rows_cols.visS = array('I', [0]) * (10)
bidir_bfs_rows_cols.visT = array('I', [0]) * (10)
bidir_bfs_rows_cols.distS = array('I', [0]) * (10)
bidir_bfs_rows_cols.distT = array('I', [0]) * (10)
bidir_bfs_rows_cols.cur = 0


def main():
    data = sys.stdin.buffer.read().split()
    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)]

    dots = 0
    for r in range(n):
        s = next(it).decode()
        add_col = rows[r].append
        for c, ch in enumerate(s):
            if ch == '.':
                add_col(c)
                cols[c].append(r)
                dots += 1

    N = n + m
    dsu = DSU(N)
    for r in range(n):
        for c in rows[r]:
            dsu.union(r, n + c)

    HEAVY_ROW = 64
    HEAVY_COL = 64
    row_sets, row_has_set = make_sets_for_heavy(rows, HEAVY_ROW)
    col_sets, col_has_set = make_sets_for_heavy(cols, HEAVY_COL)

    size = n + m
    bidir_bfs_rows_cols.visS = array('I', [0]) * size
    bidir_bfs_rows_cols.visT = array('I', [0]) * size
    bidir_bfs_rows_cols.distS = array('I', [0]) * size
    bidir_bfs_rows_cols.distT = array('I', [0]) * size
    bidir_bfs_rows_cols.cur = 0

    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

        a, b = dsu.find(r1), dsu.find(n + c1)
        x, y = dsu.find(r2), dsu.find(n + c2)
        if not (a == x or a == y or b == x or b == y):
            out.append("-1"); continue

        if in_row(rows, row_sets, row_has_set, r1, c2) or in_row(rows, row_sets, row_has_set, r2, c1):
            out.append("2"); continue

        if rows_share_col(rows, row_sets, row_has_set, r1, r2) or cols_share_row(cols, col_sets, col_has_set, c1, c2):
            out.append("3"); continue
        if has_len4_via_rows(rows, cols, row_sets, row_has_set, col_sets, col_has_set, r1, c2) or \
           has_len4_via_cols(rows, cols, row_sets, row_has_set, col_sets, col_has_set, c1, r2):
            out.append("4"); continue
        dist_edges = bidir_bfs_rows_cols(n, m, rows, cols, (r1, n + c1), (r2, n + c2))
        out.append(str(dist_edges + 1) if dist_edges != -1 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: TIME LIMIT EXCEEDED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: ACCEPTED

Test 27

Group: 5

Verdict: ACCEPTED