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)])



def get_neighbors(node_x, node_y):
    neighbors = set()

    for x in range(width):
        if grid[node_y][x] == "." and x != node_x:
            neighbors.add((x, node_y))

    for y in range(height):
        if grid[y][node_x] == "." and y != node_y:
            neighbors.add((node_x, y))

    return list(neighbors)

def reconstructPath(start_x, start_y, end_x, end_y, previous):
    path = []

    at = (end_x, end_y)

    while at is not None:
        path.append(at)
        at = previous.get(at)
    
    path.reverse()

    if path[0] == (start_x, start_y):
        return path
    
    return []

def solve(start_x, start_y):
    queue = deque()
    queue.append((start_x, start_y))

    visited_nodes = {}

    for y in range(height):
        for x in range(width):
            visited_nodes[(x, y)] = False
    
    visited_nodes[(start_x, start_y)] = True

    previous = {}

    while queue:
        node_x, node_y = queue.popleft()
        neighbors = get_neighbors(node_x, node_y)

        for next in neighbors:
            if not visited_nodes[next]:
                queue.append(next)
                visited_nodes[next] = True
                previous[next] = (node_x, node_y)
        
    return previous


def bfs(start_x, start_y, end_x, end_y):
    previous = solve(start_x, start_y)

    return reconstructPath(start_x, start_y, end_x, end_y, previous)


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

    print(len(path) - 1)

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

Test 7

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

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

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

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