Hypyt

from collections import deque

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

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

# read the questions from input
questions = []
for _ in range(question_count):
    data = input().split(" ")
    # convert 1-based Y1 X1 Y2 X2 to 0-based [(X2, Y2), (X2, Y2)]
    questions.append([(int(data[1]) - 1, int(data[0]) - 1), (int(data[3]) - 1, int(data[2]) - 1)])



# Build adjacency list for bipartite graph
adj = [[] for _ in range(height + width)]

for y in range(height):
    for x in range(width):
        if grid[y][x] == '.':
            row_node = y
            col_node = height + x
            adj[row_node].append(col_node)
            adj[col_node].append(row_node)



def bfs(start_x, start_y, end_x, end_y):
    # same cell
    if start_x == end_x and start_y == end_y:
        return 0

    # same row or column directly visible
    if start_y == end_y:
        for x in range(min(start_x, end_x), max(start_x, end_x) + 1):
            if grid[start_y][x] == '*':
                break
        else:
            return 1
    if start_x == end_x:
        for y in range(min(start_y, end_y), max(start_y, end_y) + 1):
            if grid[y][start_x] == '*':
                break
        else:
            return 1

    # --- BFS in bipartite graph ---
    start_nodes = [start_y, height + start_x]
    target_nodes = {end_y, height + end_x}

    dist = [-1] * (height + width)
    q = deque()

    for s in start_nodes:
        dist[s] = 0
        q.append(s)

    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)

    candidates = [dist[t] for t in target_nodes if dist[t] != -1]
    if not candidates:
        return -1
    return (min(candidates) + 1) // 2



# process questions
for question in questions:
    start_x, start_y = question[0]
    end_x, end_y = question[1]
    result = bfs(start_x, start_y, end_x, end_y)

    print(result)

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

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

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: TIME LIMIT EXCEEDED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 23

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 24

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED