Hypyt

import sys
input = sys.stdin.readline


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

n, m, q = map(int, input().split())
grid = [input().strip() for _ in range(n)]
id = [[-1]*m for _ in range(n)]
cells = []
k = 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == '.':
            id[i][j] = k
            cells.append((i, j))
            k += 1

dsu = DSU(k)

for i in range(n):
    j = 0
    while j < m:
        if grid[i][j] == '*':
            j += 1
            continue
        start = j
        while j < m and grid[i][j] == '.':
            j += 1
        for x in range(start, j-1):
            dsu.union(id[i][x], id[i][x+1])

for j in range(m):
    i = 0
    while i < n:
        if grid[i][j] == '*':
            i += 1
            continue
        start = i
        while i < n and grid[i][j] == '.':
            i += 1
        for y in range(start, i-1):
            dsu.union(id[y][j], id[y+1][j])

row_sets = [set() for _ in range(k)]
col_sets = [set() for _ in range(k)]
for i, (r, c) in enumerate(cells):
    root = dsu.find(i)
    row_sets[root].add(r)
    col_sets[root].add(c)

rows_to_components = [[] for _ in range(n)]
cols_to_components = [[] for _ in range(m)]
for idx in range(k):
    root = dsu.find(idx)
    for r in row_sets[root]:
        rows_to_components[r].append(root)
    for c in col_sets[root]:
        cols_to_components[c].append(root)

for _ in range(q):
    y1, x1, y2, x2 = map(lambda x: int(x)-1, input().split())
    if id[y1][x1] == -1 or id[y2][x2] == -1:
        print(-1)
        continue
    a = dsu.find(id[y1][x1])
    b = dsu.find(id[y2][x2])

    if a == b:
        print(0)
        continue

    found = False
    if y1 == y2:
        print(1)
        continue
    if x1 == x2:
        print(1)
        continue
    if any(b in rows_to_components[r] for r in row_sets[a]) or any(b in cols_to_components[c] for c in col_sets[a]):
        print(1)
        continue

    found = False
    for r in row_sets[a]:
        for comp in rows_to_components[r]:
            if b in row_sets[comp] or b in col_sets[comp]:
                found = True
                break
        if found: break
    if not found:
        for c in col_sets[a]:
            for comp in cols_to_components[c]:
                if b in row_sets[comp] or b in col_sets[comp]:
                    found = True
                    break
            if found: break

    print(2 if found else -1)

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 6

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 24

Group: 5

Verdict: WRONG ANSWER

Test 25

Group: 5

Verdict: WRONG ANSWER

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED