Câu hỏi:
13/07/2024 551
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 ?
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 ?
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
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ó.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Phân nhóm người nghi nhiễm Covid-19
Một nhóm gồm 7 người được đánh số từ 0 đến 6, có một số cặp người thường xuyên tiếp xúc trao đổi với nhau được mô tả như trong Hình 1. Một ngày, người 0 xét nghiệm và được xác định là bị nhiễm COVID-19, người ta cần phân 7 người thành các nhóm, người 0 sẽ thuộc nhóm FO, những người tiếp xúc với người ở nhóm FO sẽ được xếp vào nhóm F1, những người tiếp xúc với người ở nhóm 1-1 sẽ được xếp vào nhóm 12,....
Nhiệm vụ: Dùng thuật toán duyệt đồ thị theo chiều rộng bắt đầu từ người 0 để phân nhóm người nghi nhiễm COVID-19.
Phân nhóm người nghi nhiễm Covid-19
Một nhóm gồm 7 người được đánh số từ 0 đến 6, có một số cặp người thường xuyên tiếp xúc trao đổi với nhau được mô tả như trong Hình 1. Một ngày, người 0 xét nghiệm và được xác định là bị nhiễm COVID-19, người ta cần phân 7 người thành các nhóm, người 0 sẽ thuộc nhóm FO, những người tiếp xúc với người ở nhóm FO sẽ được xếp vào nhóm F1, những người tiếp xúc với người ở nhóm 1-1 sẽ được xếp vào nhóm 12,....
Nhiệm vụ: Dùng thuật toán duyệt đồ thị theo chiều rộng bắt đầu từ người 0 để phân nhóm người nghi nhiễm COVID-19.
Xem đáp án »
13/07/2024
93
Bình luận
🔥 Đề thi HOT:
-
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 7: HTML và cấu trúc trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
-
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
-
Đề thi Học kì 1 Tin học 12 có đáp án (Đề 1)
về câu hỏi!