Bài toán Tìm đường đi trong mê cung trang 69 Chuyên đề Tin học 12

Giải Chuyên đề Tin 12 Bài 5: Thực hành duyệt đồ thị - Cánh diều

Vận dụng trang 69 Chuyên đề Tin học 12: Bài toán Tìm đường đi trong mê cung

Nam đang chơi trò chơi tìm đường đi trong mê cung như trong Hình 5. Dùng thuật toán duyệt đồ thị theo chiều sâu đề kiểm tra: Nam có thể đi vào mê cung từ góc trái trên và ra khỏi mê cung ở góc phải dưới hay không ?

Lời giải:

Xây dựng đồ thị, đánh số các ô trong mê cung (Hình 6), mỗi ô tương ứng

một đỉnh của đồ thị, hai ô kể cạnh có cạnh nối. Theo như Hình 6, đồ thị có 50 đỉnh. Duyệt đồ thị theo chiều sâu bắt đầu từ ô số 1 theo thứ tự ưu tiên đi theo ô xuống dưới, sang phải, lên trên, sang trái.

Mã giả để giải bài toán tìm đường đi trong mê cung sử dụng thuật toán duyệt đồ thị theo chiều sâu (DFS):

def dfs(maze, start, end):

    stack = [(start, [start])]

    visited = set()

    while stack:

        (vertex, path) = stack.pop()

        if vertex in visited:

            continue

       visited.add(vertex)

        for neighbor in get_neighbors(maze, vertex):

            if neighbor == end:

                return path + [end]

           stack.append((neighbor, path + [neighbor]))

    return None

def get_neighbors(maze, cell):

    # Giả sử hàm này trả về danh sách các ô kề cạnh có thể đi được từ ô hiện tại

    pass

# Giả sử maze là một mảng hai chiều biểu diễn mê cung, start và end là vị trí bắt đầu và kết thúc

path = dfs(maze, start, end)

if path:

    print("Có đường đi từ góc trái trên đến góc phải dưới.")

else:

    print("Không có đường đi.")

Lưu ý: 

Cần xác định cấu trúc dữ liệu maze phù hợp và viết hàm get_neighbors để lấy các ô kề cạnh có thể đi được từ một ô bất kỳ trong mê cung. Mã giả trên chỉ là khung sườn cơ bản, bạn cần điều chỉnh để phù hợp với dữ liệu cụ thể của bài toán bạn đang giải quyết. Đồ thị mê cung cụ thể cần được xây dựng dựa trên hình ảnh mê cung bạn có.

Lời giải bài tập Chuyên đề Tin 12 Bài 5: Thực hành duyệt đồ thị hay, chi tiết khác:

• Chuyên đề Tin học 12 Bài toán trang 69 Chuyên đề Tin học 12: Phân nhóm người nghi nhiễm Covid-19 ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Cánh diều hay, chi tiết khác:

• Chuyên đề Tin học 12 Bài 1: Đồ thị, phân loại đồ thị

• Chuyên đề Tin học 12 Bài 2: Biểu diễn đồ thị trên máy tính

• Chuyên đề Tin học 12 Bài 3: Thực hành các thao tác cơ bản với đồ thị trên máy tính

• Chuyên đề Tin học 12 Bài 4: Duyệt đồ thị

• Chuyên đề Tin học 12 Bài 6: Dự án học tập: Tìm hiểu các vấn đề ứng dụng đồ thị

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---