Hỏi đáp
Chia sẻ kiến thức, cùng nhau phát triển
Cách tìm đường đi ngắn nhất bằng thuật toán dijstra
20:30 16-01-2025
477 lượt xem
1 bình luận
28 | 21 | 14 | e | 7 | i | ||||||
27 | a | 20 | 13 | 6 | |||||||
26 | f | 19 | d | 12 | 5 | ||||||
25 | 18 | 11 | 4 | ||||||||
24 | 17 | 10 | 3 | h | |||||||
c | 23 | 16 | 9 | 2 | |||||||
22 | 15 | b | 8 | g | 1 | ||||||
0 |
Làm sao có thể tìm được khoảng cách từ 0 tới các vị trí a, b, c, d, e, f, g, h, i tương ứng với các số trong ô tương ứng, với mỗi 1 ô là 1 đơn vị, chúng ta chỉ có thể đi dọc theo các cột đánh số, và 2 hàng ngang trên cùng và dưới cùng
Mong mọi người có thể giải đáp giúp em ạ.
def calculate_distance(start, target):
"""
Tính khoảng cách từ vị trí start đến vị trí target theo quy tắc bài toán.
"""
row0, col0 = start
row, col = target
if col0 == col:
# Cùng cột: chỉ di chuyển dọc
return abs(row0 - row)
else:
# Khác cột: cần đi qua hàng trên cùng (28) hoặc dưới cùng (0)
through_top = abs(row0 - 28) + abs(row - 28) + abs(col0 - col)
through_bottom = abs(row0 - 0) + abs(row - 0) + abs(col0 - col)
return min(through_top, through_bottom)
# Tọa độ của các ký tự trên bảng
positions = {
'a': (27, 1), 'b': (15, 3), 'c': (24, 0), 'd': (19, 3),
'e': (28, 4), 'f': (26, 2), 'g': (8, 6), 'h': (3, 8), 'i': (28, 7), '0': (0, 8)
}
# Vị trí bắt đầu (ô 0)
start = positions['0']
# Tính khoảng cách từ 0 đến từng ký tự
distances = {char: calculate_distance(start, pos) for char, pos in positions.items() if char != '0'}
# Hiển thị kết quả
for char, distance in distances.items():
print(f"Khoảng cách từ 0 đến {char}: {distance}")