Ở phần trước mình đã chia sẻ một số khả năng ứng dụng của 2 thuật toán tìm kiếm BFS và DFS, ở phần này mình xin nêu ra một ví dụ cụ thể về bài toán tìm đường đi ngắn nhất giửa 2 đỉnh trong cùng một tập đồ thị liên thông.
Ví dụ về một bài toán lan bom:
Cho một thành phố (đồ thị) biểu diễn bởi một ma trận 2 chiều MxN gồm các giá trị 0 và 1 (ma trận kề của đồ thị). Tọa độ của bom sẽ được cho trước, bom sẽ lan theo 4 hướng(trên - dưới - trái - phải). Bom chỉ lan khi gặp 1 và thời gian để lan tới 1 điểm bên cạnh là 1s. Bài toán yêu cầu tính thời gian để quả lan toàn bộ các điểm cạnh nó.
ví dụ input là một ma trận 7x8 và bom ở vị trí 2 5
0 0 1 1 0 0 0
1 1 1 1 0 1 0
0 0 1 1 1 1 1
0 1 1 1 1 1 1
0 1 0 0 1 1 0
0 1 1 1 1 0 0
0 0 1 0 1 1 1
0 0 0 0 1 0 0
khi bom lan hết sẽ được biểu diễn như ma trận như dưới đây
0 0 6 7 0 0 0 0
7 6 5 6 0 8 0 0
0 0 4 5 6 7 8 0
0 2 3 4 5 6 7 0
0 1 0 0 6 7 0 0
0 2 3 4 5 0 0 0
0 0 4 0 6 7 8 0
Nhìn ma trân trên ta thấy rằng thời gian để bom lan hết có thể là 8s, kết quả sẽ là 8.
Phân tích: ở bài toán này, chúng ta sẽ sử dụng thuật toán BFS, sẽ duyệt rộng dần từ điểm thả bom, khi bom lan đến điểm nào thì giá trị của điểm đó sẽ tăng lên 1 giá trị (giá trị sẽ bằng giá trị điểm lan + 1), ta cần một biến max để lưu giá trị lớn nhất, và kết quả sẽ là giá trị lớn nhất khi ta duyệt hết các điểm. Lưu ý rằng ta cần check để mỗi điểm chi được duyệt một lần.
***Nếu quy bài toán này về bài toán tìm đường đi ngắn nhất giữa 2 điểm thì điểm xuất phát chính là điểm thả bom còn độ dài đường đi ngắn nhất chính là thời gian bom lan đến điểm đích.
chi tiết cài đặt bài toán và file input được đính kèm, các bạn có thể tham khảo.
Ví dụ về một bài toán lan bom:
Cho một thành phố (đồ thị) biểu diễn bởi một ma trận 2 chiều MxN gồm các giá trị 0 và 1 (ma trận kề của đồ thị). Tọa độ của bom sẽ được cho trước, bom sẽ lan theo 4 hướng(trên - dưới - trái - phải). Bom chỉ lan khi gặp 1 và thời gian để lan tới 1 điểm bên cạnh là 1s. Bài toán yêu cầu tính thời gian để quả lan toàn bộ các điểm cạnh nó.
ví dụ input là một ma trận 7x8 và bom ở vị trí 2 5
0 0 1 1 0 0 0
1 1 1 1 0 1 0
0 0 1 1 1 1 1
0 1 1 1 1 1 1
0 1 0 0 1 1 0
0 1 1 1 1 0 0
0 0 1 0 1 1 1
0 0 0 0 1 0 0
khi bom lan hết sẽ được biểu diễn như ma trận như dưới đây
0 0 6 7 0 0 0 0
7 6 5 6 0 8 0 0
0 0 4 5 6 7 8 0
0 2 3 4 5 6 7 0
0 1 0 0 6 7 0 0
0 2 3 4 5 0 0 0
0 0 4 0 6 7 8 0
Nhìn ma trân trên ta thấy rằng thời gian để bom lan hết có thể là 8s, kết quả sẽ là 8.
Phân tích: ở bài toán này, chúng ta sẽ sử dụng thuật toán BFS, sẽ duyệt rộng dần từ điểm thả bom, khi bom lan đến điểm nào thì giá trị của điểm đó sẽ tăng lên 1 giá trị (giá trị sẽ bằng giá trị điểm lan + 1), ta cần một biến max để lưu giá trị lớn nhất, và kết quả sẽ là giá trị lớn nhất khi ta duyệt hết các điểm. Lưu ý rằng ta cần check để mỗi điểm chi được duyệt một lần.
***Nếu quy bài toán này về bài toán tìm đường đi ngắn nhất giữa 2 điểm thì điểm xuất phát chính là điểm thả bom còn độ dài đường đi ngắn nhất chính là thời gian bom lan đến điểm đích.
chi tiết cài đặt bài toán và file input được đính kèm, các bạn có thể tham khảo.
