unknowpc90
Junior Member
Chào các bác,
Em đang cần giải quyết một thuật toán tìm đường đi trong lập trình
Yêu cầu là tìm đường đi từ A đến B và tất cả các đường có kết nối với quãng đường cần đi đó, mỗi điểm trên đường đi đều có toạ độ (x,y)
Nó giống như dòng nước sẽ chảy từ nguồn nước đến bên ngoài thông qua hệ thống uống nước và yêu cầu tìm tất cả đường đi mà nước có thể chạm tới.
Ví dụ như hình:
Theo hình trên, nước sẽ chảy từ trái qua phải (chảy tới vùng màu vàng), vì thế điểm bắt đầu là (1,3) và chảy đến điểm cuối là (5,6). Trên đường đi, nước sẽ chảy qua các điểm khác. Tất cả điểm nước chảy qua được đều tô màu đỏ
Khả năng hiện có: có thể xác định điểm đầu là (1,3) và điểm cuối là (5,6). Có thể xác định những điểm kết nối với nó, chẳng hạn điểm đầu là (1,3) thì có thể biết điểm kết nối với nó là (2,3).
Như hình trên, kết quả của thuật toán em mong muốn sẽ trả về 3 chuỗi:
Chuỗi 1: (1,3), (2,3), (2,4), (2,5), (3,5), (3,6), (4,6), (5,6) [đường đi nước chảy từ điểm đầu đến điểm cuối]
Chuỗi 2: (1,3), (2,3), (2,4), (2,5), (3,5), (3,6), (3,7), (3,8), (2,8) [đường đi nước có thể chảy lan tới]
Chuỗi 3: (1,3), (2,3), (2,2), (2,1), (3,1) [đường đi nước có thể chảy lan tới]
Các bác góp ý cách viết thuật toán cho em nhé. Thanks!
Em đang cần giải quyết một thuật toán tìm đường đi trong lập trình
Yêu cầu là tìm đường đi từ A đến B và tất cả các đường có kết nối với quãng đường cần đi đó, mỗi điểm trên đường đi đều có toạ độ (x,y)
Nó giống như dòng nước sẽ chảy từ nguồn nước đến bên ngoài thông qua hệ thống uống nước và yêu cầu tìm tất cả đường đi mà nước có thể chạm tới.
Ví dụ như hình:
Theo hình trên, nước sẽ chảy từ trái qua phải (chảy tới vùng màu vàng), vì thế điểm bắt đầu là (1,3) và chảy đến điểm cuối là (5,6). Trên đường đi, nước sẽ chảy qua các điểm khác. Tất cả điểm nước chảy qua được đều tô màu đỏ
Khả năng hiện có: có thể xác định điểm đầu là (1,3) và điểm cuối là (5,6). Có thể xác định những điểm kết nối với nó, chẳng hạn điểm đầu là (1,3) thì có thể biết điểm kết nối với nó là (2,3).
Như hình trên, kết quả của thuật toán em mong muốn sẽ trả về 3 chuỗi:
Chuỗi 1: (1,3), (2,3), (2,4), (2,5), (3,5), (3,6), (4,6), (5,6) [đường đi nước chảy từ điểm đầu đến điểm cuối]
Chuỗi 2: (1,3), (2,3), (2,4), (2,5), (3,5), (3,6), (3,7), (3,8), (2,8) [đường đi nước có thể chảy lan tới]
Chuỗi 3: (1,3), (2,3), (2,2), (2,1), (3,1) [đường đi nước có thể chảy lan tới]
Các bác góp ý cách viết thuật toán cho em nhé. Thanks!
Last edited: