Cho ma trận kí tự MxN với kích thước k vượt quá 100x100. Hãy kiểm tra sự tồn tại của chuỗi “ALLIZZWELL” trong ma trận đó. Đường dẫn có thể được tìm thấy theo hàng ngang, dọc và đường chéo.
Giải thuật:
Sử dụng Backtrack không nhớ để kiểm tra sự tồn tại của chuỗi.
Hàm backtrack sẽ truyền vào số kí tự đã được tìm thấy của chuỗi “ALLIZZWELL” để lựa chọn kí tự tiếp theo.
Ví dụ ban đầu count = 0 thì sẽ tìm kí tự 'A', khi tìm thấy A count sẽ tăng lên 1 để tìm kiếm kí tự 'L' và tiếp tục đến khi tìm được chuỗi.
Sau khi tìm thấy thì ta sẽ dùng 1 cờ (flag) để thoát nhanh khỏi hàm đê quy.
Giải thuật:
Sử dụng Backtrack không nhớ để kiểm tra sự tồn tại của chuỗi.
Hàm backtrack sẽ truyền vào số kí tự đã được tìm thấy của chuỗi “ALLIZZWELL” để lựa chọn kí tự tiếp theo.
Ví dụ ban đầu count = 0 thì sẽ tìm kí tự 'A', khi tìm thấy A count sẽ tăng lên 1 để tìm kiếm kí tự 'L' và tiếp tục đến khi tìm được chuỗi.
Sau khi tìm thấy thì ta sẽ dùng 1 cờ (flag) để thoát nhanh khỏi hàm đê quy.
Solution C++4.3.2