Hypyt

import sys
from collections import deque

def readints():
  return list(map(int, sys.stdin.readline().split()))

def distance_calc(n, m, row_to_cols, col_to_rows, spawns, targets):
  targets_set = set(targets)
  for s in spawns:
    if s in targets_set:
      return 0

  N = n + m
  dist1 = [-1] * N
  dist2 = [-1] * N
  q1 = deque()
  q2 = deque()

  for s in spawns:
    dist1[s] = 0
    q1.append(s)
  for t in targets:
    dist2[t] = 0
    q2.append(t)

  INF = 10**18
  best = INF

  while q1 and q2:
    if len(q1) <= len(q2):
      u = q1.popleft()
      du = dist1[u]
      if du >= best: 
        continue

      if u < n:
        for cx in row_to_cols[u]:
          v = n + cx
          if dist1[v] == -1:
            dist1[v] = du + 1
            q1.append(v)
            if dist2[v] != -1:
              total = dist1[v] + dist2[v]
              if total < best:
                best = total
      else:
        col_index = u - n
        for ry in col_to_rows[col_index]:
          v = ry
          if dist1[v] == -1:
            dist1[v] = du + 1
            q1.append(v)
            if dist2[v] != -1:
              total = dist1[v] + dist2[v]
              if total < best:
                best = total
    else:
      u = q2.popleft()
      du = dist2[u]
      if du >= best:
        continue

      if u < n:
        for cx in row_to_cols[u]:
          v = n + cx
          if dist2[v] == -1:
            dist2[v] = du + 1
            q2.append(v)
            if dist1[v] != -1:
              total = dist1[v] + dist2[v]
              if total < best:
                best = total
      else:
        col_index = u - n
        for ry in col_to_rows[col_index]:
          v = ry
          if dist2[v] == -1:
            dist2[v] = du + 1
            q2.append(v)
            if dist1[v] != -1:
              total = dist1[v] + dist2[v]
              if total < best:
                best = total

  return best if best != INF else -1

def main():
  data = sys.stdin.read().strip().splitlines()

  it = iter(data)
  n, m, q = map(int, next(it).split())
  grid = [list(next(it).rstrip()) for _ in range(n)]

  row_to_cols = [[] for _ in range(n)]
  col_to_rows = [[] for _ in range(m)]
  for y in range(n):
    row = grid[y]
    for x, ch in enumerate(row):
      if ch == '.':
        row_to_cols[y].append(x)
        col_to_rows[x].append(y)

  N = n + m
  neighbors = [[] for _ in range(N)]
  for y in range(n):
    for x in row_to_cols[y]:
      ry = y
      cx = n + x
      neighbors[ry].append(cx)
      neighbors[cx].append(ry)

  dist = [[-1] * N for _ in range(N)]
  dq = deque()
  for s in range(N):
    if not neighbors[s]:
      dist[s][s] = 0
      continue
    drow = dist[s]
    drow[s] = 0
    dq.clear()
    dq.append(s)
    while dq:
      u = dq.popleft()
      nu = drow[u] + 1
      for v in neighbors[u]:
        if drow[v] == -1:
          drow[v] = nu
          dq.append(v)

  output = []
  for _ in range(q):
    y1, x1, y2, x2 = map(int, next(it).split())
    y1 -= 1; x1 -= 1; y2 -= 1; x2 -= 1

    if grid[y1][x1] != '.' or grid[y2][x2] != '.':
      output.append("-1")
      continue

    if y1 == y2 and x1 == x2:
      output.append("0")
      continue

    Ry1 = y1
    Cx1 = n + x1
    Ry2 = y2
    Cx2 = n + x2

    dmin = 10**9
    d = dist[Ry1][Ry2]
    if d != -1 and d < dmin: dmin = d
    d = dist[Ry1][Cx2]
    if d != -1 and d < dmin: dmin = d
    d = dist[Cx1][Ry2]
    if d != -1 and d < dmin: dmin = d
    d = dist[Cx1][Cx2]
    if d != -1 and d < dmin: dmin = d

    if dmin == 10**9:
      output.append("-1")
    else:
      output.append(str(1 + dmin))

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

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

Test 20

Group: 5

Verdict: ACCEPTED

Test 21

Group: 5

Verdict: ACCEPTED

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