Kết nối các con bò

Lời giải: Kết nối các con bò

Hướng tiếp cận

Vì $N\le 10$ nên $N!\le 3,628,800$. Ta có thể duyệt toàn bộ hoán vị của $N$ điểm và kiểm tra từng hoán vị có hợp lệ không.

Nhận xét quan trọng

1. Mỗi đoạn đường phải song song với trục tọa độ — nếu hai điểm liên tiếp không cùng $x$ và không cùng $y$ thì hoán vị đó vô hiệu.
2. Hướng di chuyển vào và ra khỏi mỗi điểm thăm phải khác nhau.
3. Cần kiểm tra đủ $N+1$ đoạn: gốc $\to$ điểm 1 $\to$ điểm 2 $\to$ ... $\to$ điểm $N$ $\to$ gốc.

Thuật toán

1. Sinh tất cả hoán vị của $N$ điểm (dùng backtracking).
2. Với mỗi hoán vị, xác định hướng của từng đoạn đường (Bắc/Nam/Đông/Tây hoặc không hợp lệ).
3. Hoán vị hợp lệ khi:
   • Tất cả đoạn đường đều hợp lệ (song song trục).
   • Tại mỗi điểm thăm, hướng vào $\ne$ hướng ra.
4. Đếm số hoán vị hợp lệ.

Độ phức tạp

• Thời gian: $O(N·N!)$
• Bộ nhớ: $O(N)$