temp.py - master - k2709/matrix_task

temp.py
67 строк3 KB
urik
Work on short path in matrix continue
12 янв 2025, 18:11
12 янв 2025, 18:1115b08ae
def display_matrix(matrix, start, end):
    rows, cols = len(matrix), len(matrix[0])
    cell_size = 40

    def draw_matrix():
        for i in range(rows):
            for j in range(cols):
                color = "white" if matrix[i][j] == 0 else "black"
                canvas.create_rectangle(j * cell_size, i * cell_size, (j + 1) * cell_size, (i + 1) * cell_size, fill=color, outline="gray")

    result_window = tk.Toplevel(root)
    result_window.title("Matrix Visualization")

    canvas = tk.Canvas(result_window, width=cols * cell_size, height=rows * cell_size)
    canvas.pack()

    step_label = tk.Label(result_window, text="Количество шагов: 0")
    step_label.pack()

    draw_matrix()
    path = shortest_path(matrix, start, end, canvas, cell_size, step_label)

    if path:
        visualize_path(matrix, path, canvas, cell_size)

    if path:
        tk.Label(result_window, text=f"Path length: {len(path) - 1}").pack()
    else:
        tk.Label(result_window, text="Path not found").pack()

def shortest_path(matrix, start, end, canvas, cell_size, step_label):
    rows, cols = len(matrix), len(matrix[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Вверх, вниз, влево, вправо
    queue = deque([(start[0], start[1], 0, [start])])  # (row, col, distance, path)
    visited = set()
    step_count = 0  # Счетчик шагов

    while queue:
        row, col, dist, path = queue.popleft()
        step_count += 1  # Увеличиваем счетчик шагов

        # Обновляем текст с количеством шагов
        step_label.config(text=f"Количество шагов: {step_count}")

        if (row, col) in visited or matrix[row][col] == 1:
            continue  # Пропускаем заблокированные или уже посещённые ячейки

        visited.add((row, col))

        # Визуализация текущей ячейки
        i, j = path[-1][0], path[-1][1]
        canvas.create_rectangle(j * cell_size, i * cell_size, (j + 1) * cell_size, (i + 1) * cell_size,
                                fill="blue")
        canvas.update()
        canvas.after(100)

        if (row, col) == end:
            print(f"Количество шагов поиска пути: {step_count}")
            return path  # Возвращаем путь

        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            if 0 <= new_row < rows and 0 <= new_col < cols:
                queue.append((new_row, new_col, dist + 1, path + [(new_row, new_col)]))

    print(f"Количество шагов поиска пути: {step_count}")
    return None  # Если путь не найден