Hướng dẫn giải của Xây cổng
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: Xây cổng
Thuật toán
- Nhân đôi tọa độ để rào chiếm ô trên lưới (tránh hai vùng kề nhau qua cạnh rào bị coi là liên thông).
- Đánh dấu tất cả ô rào trên lưới.
- Flood fill (BFS/DFS) đếm số vùng trống liên thông.
- Đáp án = số vùng - 1.
Bình luận