Hướng dẫn giải của Kết nối các con bò

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.

Tác giả: huunguyen

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

Hướng tiếp cận

Vì $N \leq 10$ nên $N! \leq 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

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.
Hướng di chuyển vào và ra khỏi mỗi điểm thăm phải khác nhau.
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

Sinh tất cả hoán vị của $N$ điểm (dùng backtracking).
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ệ).
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 $\neq$ hướng ra.
Đếm số hoán vị hợp lệ.

Độ phức tạp

Thời gian: $O (N \cdot N!)$
Bộ nhớ: $O (N)$

Bình luận

Không có bình luận tại thời điểm này.