I. Giới Thiệu Chung
Trong những chuyên đề trước, chúng ta đã tìm hiểu về hai cấu trúc dữ liệu cơ bản là ngăn xếp và hàng đợi. Trong bài này, chúng ta sẽ khám phá một bài toán ứng dụng hấp dẫn, thường gặp trong các kỳ thi lập trình ở cấp THCS và THPT, đó là bài toán Loang trên Ma Trận. Phương pháp giải bài toán này sử dụng thuật toán Tìm Kiếm Theo Chiều Sâu (BFS) trên đồ thị, nhưng cách áp dụng lên ma trận sẽ dễ hiểu hơn, giúp bạn nào chưa học về đồ thị vẫn có thể nắm bắt và làm bài.
Phát Biểu Bài Toán
Cho một ma trận có m hàng và n cột, với các ô mang giá trị 0 hoặc 1, trong đó 0 nghĩa là có thể đi vào và 1 nghĩa là không thể đi vào. Bắt đầu từ ô (x1, y1), bạn phải tìm đường đi ngắn nhất tới ô (x2, y2) với các quy tắc di chuyển có thể là lên, xuống, trái hoặc phải. Độ dài đường đi được tính bằng tổng số ô trên đường đi, bao gồm cả ô xuất phát và ô kết thúc.
Input:
- Dòng đầu tiên chứa hai số nguyên dương m,n.
- Tiếp theo là m dòng, mỗi dòng chứa một dãy gồm n số thuộc hai giá trị 0-1 thể hiện ma trận.
- Dòng cuối cùng chứa bốn số nguyên dương x1, y1, x2, y2.
Output:
- Dòng đầu tiên là số nguyên duy nhất là độ dài đường đi ngắn nhất. Nếu không thể di chuyển được, thì in ra -1.
- Nếu tồn tại đường đi, in ra tọa độ các ô trên đường đi.
Ví dụ:
Input:
5 5
0 1 0 0 0
0 0 1 0 1
0 0 0 1 0
0 1 0 0 0
0 1 0 0 1
1 1 5 3Output:
7
1 1
2 1
3 1
3 2
3 3
4 3
5 3Phương Pháp Giải
Với sâu hơn, khi đứng ở ô (x,y), bạn có thể di chuyển tới các ô (x-1,y), (x,y-1), (x+1,y), (x,y+1). Ý tưởng là sử dụng hàng đợi để lưu danh sách các ô trên mọi đường đi có thể xuất hiện trên bảng. Đường đi nào tới được ô đích trước tiên chính là đường đi ngắn nhất. Để theo dõi độ dài đường đingắn nhất đến một ô, sử dụng mảng dp[x][y], nghĩa là độ dài đường đi ngắn nhất tính từ ô xuất phát (x1,y1) đến ô (x,y). Bắt đầu với chỉ ô xuất phát, áp dụng quá trình:
- Lấy thành phần ở đầu hàng đợi ra và duyệt qua các ô lân cận, nếu ô hợp lệ thì thêm vào hàng đợi và cập nhật độ dài.
- Tiếp tục như vậy cho đến khi tìm thấy ô đích.
Nếu ô đích được kết nối, in ra độ dài và đường đi, nếu không, in -1.
Đánh Giá Độ Phức Tạp
Khi mỗi ô chỉ được di chuyển vào hoặc ra từ hàng đợi một lần, độ phức tạp của thuật toán là O(m × n).
Xử Lý Các Trường Hợp Áp Dụng
Ngoài bài toán cơ bản, có nhiều bài toán áp dụng khác như xác định bồn hoa lớn nhất trên ma trận hay di chuyển trên sao Hỏa với điều kiện độ cao giữa các ô. Những bài toán này đều có thể giải quyết bằng cách sử dụng các kỹ thuật tương tự mà chúng ta đã học được từ bài toán loang trên ma trận.
Khám phá và ứng dụng các kiến thức này không chỉ giúp bạn nâng cao kỹ năng lập trình mà còn tăng khả năng giải quyết vấn đề trong thực tế.
source: viblo
