Combinatorial Method for Shortest Path Counting
Để giải quyết bài toán này, chúng ta sẽ sử dụng phương pháp tổ hợp để tìm số lượng đường đi ngắn nhất từ A đến B trên lưới đường đã cho, bỏ qua khu vực VVV là khu vực cấm đi qua.
Trước hết, chúng ta chia bài toán thành hai phần:
1. Đi từ A đến cạnh trên cùng của khu vực VVV.
2. Tiếp tục đi từ cạnh trên của khu vực VVV đến B.
Trong mỗi phần, chúng ta sẽ điều hướng qua các ô lưới - đi xuống (D) hoặc đi sang phải (R). Số lượng đường đi ngắn nhất sẽ tương ứng với số cách sắp xếp các bước D và R sao cho đạt được điểm đến mà không quan tâm đến các ràng buộc của khu vực cấm.
Đếm số bước D và R từ A đến cạnh trên cùng của VVV, cách điểm A 3 bước sang phải và 2 bước xuống, tức là RRRDD. Độ dài của đường đi không đổi, do đó chúng ta chỉ quan tâm đến số cách sắp xếp các chữ R và D. Số cách sắp xếp 5 chữ cái với 3 chữ R và 2 chữ D là:
C(5,3) = C(5,2) = 5! / (3!2!) = (5 * 4) / (2 * 1) = 10 cách.
Tương tự, từ cạnh trên của VVV đến B, ta cần đi thêm 3 bước sang phải và 2 bước xuống, vì vậy lại có 10 cách nữa để sắp xếp các bước.
Vậy, tổng số đường đi ngắn nhất là số cách sắp xếp từ A đến VVV nhân với số cách sắp xếp từ VVV đến B, tức là:
10 * 10 = 100 đường đi ngắn nhất từ A đến B mà không đi qua khu vực cấm VVV.
