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 ạ.

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Speedfight đã bình luận 17:07 27-01-2025

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}")

Câu hỏi mới nhất