Móng ngựa

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

1. Vì $N\le 5$, lưới tối đa $5\times 5=25$ ô — không gian tìm kiếm nhỏ.
2. Chuỗi hợp lệ dạng $k$ dấu ( + $k$ dấu ): chỉ cần thu thập ( liên tục đến khi gặp ), rồi chỉ thu thập ).
3. Cắt tỉa: nếu đã vào pha ) và $\text{numopen}=\text{numclose}$, dừng.

Thuật toán

DFS từ $(0,0)$ với trạng thái $(x,y,\text{open},\text{close},\text{closing})$:

• 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: $O(4^{N^2})$ (giới hạn thực tế nhỏ hơn nhiều do cắt tỉa)
• Bộ nhớ: $O(N^2)$