Hướng dẫn giải của Móng ngựa
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Lời giải: Móng ngựa
Hướng tiếp cận
DFS backtracking từ góc trên trái, thu thập theo hai pha: pha ( rồi pha ).
Nhận xét quan trọng
- Vì , lưới tối đa ô — không gian tìm kiếm nhỏ.
- Chuỗi hợp lệ dạng dấu
(+ dấu): chỉ cần thu thập(liên tục đến khi gặp), rồi chỉ thu thập). - Cắt tỉa: nếu đã vào pha
)và , dừng.
Thuật toán
DFS từ với trạng thái :
- Pha mở (
closing=false): có thể thu thêm(hoặc chuyển sang pha đóng. - Pha đóng (
closing=true): chỉ thu thêm).
Độ phức tạp
- Thời gian: (giới hạn thực tế nhỏ hơn nhiều do cắt tỉa)
- Bộ nhớ:
Bình luận