Hypyt

height, width, question_count = map(int, input().split())

# create the grid from input
grid = []
for _ in range(height):
    grid.append(list(input()))

# read all queries first
queries = []
for _ in range(question_count):
    # convert 1-based Y1 X1 Y2 X2 to 0-based (X2, Y2, X2, Y2)
    y1, x1, y2, x2 = map(int, input().split())
    queries.append((y1 - 1, x1 - 1, y2 - 1, x2 - 1))

node_count = height + width
adjacency_list = []
for _ in range(node_count):
    adjacency_list.append([])

for row_index in range(height):
    row = grid[row_index]

    for col_index, cell in enumerate(row):
        if cell == '.':
            row_node = row_index
            col_node = height + col_index
            
            adjacency_list[row_node].append(col_node)
            adjacency_list[col_node].append(row_node)

distances = []
for _ in range(node_count):
    distances.append([-1] * node_count)

for start_node in range(node_count):
    queue = []
    queue.append(start_node)
    distance_from_start = distances[start_node]
    distance_from_start[start_node] = 0

    while queue:
        current_node = queue.pop(0)
        current_distance = distance_from_start[current_node]

        for neighbor in adjacency_list[current_node]:
            if distance_from_start[neighbor] == -1:
                distance_from_start[neighbor] = current_distance + 1
                queue.append(neighbor)

# now process all queries
answers = []

for (start_row, start_col, end_row, end_col) in queries:
    if start_row == end_row and start_col == end_col:
        answers.append(0)
        continue

    shortest_distance = 10 ** 9 # big placeholder value for upper bound
    for start_node in (start_row, height + start_col):
        for end_node in (end_row, height + end_col):
            distance = distances[start_node][end_node]
            if distance != -1:
                shortest_distance = min(shortest_distance, distance + 1)

    answers.append(shortest_distance if shortest_distance != 10 ** 9 else -1)

for answer in answers:
    print(answer)

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