Question: Câu 7. Hình vẽ cho một ô lưới hình chữ nhật. Biết rằng chú mèo đang đứng ở nút $A$ và di chuyển về phía nút $B$ theo quy luật: • Chỉ di chuyển theo hướng thẳng đứng lên trên hoặc theo hướng ngang sang phải. • Mỗi lần chỉ di chuyển được một đoạn bằng độ dài cạnh của một hình vuông nhỏ. • Chỉ di chuyển giữa các nút được nối với nhau bởi một đoạn thẳng. • Được phép di chuyển từ $N$ đến $M$ đúng một lần dù là hướng từ phải sang trái. Trên lưới có các vùng chứa nước bẩn mô tả bởi các ô màu đen và chú mèo sẽ không thể đi chuyển xuyên qua vùng nước bẩn này nhưng được phép di chuyển trên đường biên của các vùng này. Hãy đếm số cách đi của chú mèo từ nút $A$ đến nút $B$?

1. **Đặt vấn đề:** Chúng ta cần đếm số cách đi từ nút $A$ đến nút $B$ trên một lưới hình chữ nhật với các quy tắc di chuyển: - Chỉ đi lên hoặc sang phải mỗi bước một ô. - Có vùng nước bẩn (ô đen) không thể đi qua, nhưng có thể đi trên biên. - Được phép đi ngược từ $N$ đến $M$ đúng một lần (từ phải sang trái). 2. **Phân tích:** - Thông thường, số đường đi từ $A$ đến $B$ trên lưới chỉ đi lên hoặc sang phải là bài toán đếm tổ hợp. - Tuy nhiên, vùng nước bẩn cản trở đường đi, cần loại trừ các đường đi qua ô đen. - Việc cho phép đi ngược từ $N$ đến $M$ một lần tạo ra một đường đi đặc biệt, cần tính riêng. 3. **Cách tiếp cận:** - Gọi $f(X)$ là số cách đi từ $A$ đến nút $X$ tuân theo quy tắc di chuyển lên hoặc sang phải. - Gọi $g(X)$ là số cách đi từ $X$ đến $B$ cũng theo quy tắc lên hoặc sang phải. - Tính $f$ và $g$ cho tất cả các nút không bị chặn. - Đường đi từ $A$ đến $B$ có thể chia thành 2 loại: a) Đường đi không sử dụng đoạn ngược $N \to M$. b) Đường đi sử dụng đoạn ngược $N \to M$ một lần. 4. **Tính số đường đi không dùng đoạn ngược:** - Số đường đi là tổng $\sum_{X} f(X) \times g(X)$ với $X$ là các nút trên đường đi hợp lệ không qua ô đen. 5. **Tính số đường đi dùng đoạn ngược $N \to M$ một lần:** - Đường đi sẽ đi từ $A$ đến $N$ theo quy tắc lên hoặc phải. - Sau đó đi ngược từ $N$ đến $M$ (một lần duy nhất). - Rồi từ $M$ đến $B$ theo quy tắc lên hoặc phải. - Số đường đi loại này là $f(N) \times g(M)$. 6. **Tổng số đường đi:** $$\text{Tổng} = \text{Số đường không dùng đoạn ngược} + f(N) \times g(M)$$ 7. **Lưu ý:** - Cần loại trừ các đường đi qua ô nước bẩn. - Tính $f$ và $g$ bằng quy hoạch động (dynamic programming) trên lưới, bỏ qua ô đen. 8. **Kết luận:** - Bài toán yêu cầu đếm số đường đi hợp lệ theo quy tắc trên. - Phương pháp tổng quát là dùng quy hoạch động tính $f$ và $g$, sau đó áp dụng công thức trên. **Do đề bài không cung cấp kích thước lưới và vị trí chính xác các nút, ô đen, $M$, $N$, $A$, $B$, nên không thể tính số đường đi cụ thể.** Nếu có dữ liệu cụ thể, ta sẽ: - Tạo ma trận trạng thái. - Tính $f$ từ $A$ đến mọi nút. - Tính $g$ từ mọi nút đến $B$. - Áp dụng công thức tổng. --- **Tóm lại:** - Số cách đi từ $A$ đến $B$ là $$\sum_{X} f(X) \times g(X) + f(N) \times g(M)$$ - Với $f$ và $g$ tính theo quy hoạch động không đi qua ô đen.