Hướng dẫn giải của Trượt Tuyết Việt Dã

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: Trượt Tuyết Việt Dã

Hướng tiếp cận

Tìm kiếm nhị phân trên giá trị $D$ , kết hợp BFS/DFS để kiểm tra tính liên thông của các điểm kiểm tra.

Nhận xét quan trọng

Nếu $D$ đủ lớn thì toàn bộ lưới là một thành phần liên thông, nên câu trả lời tồn tại.
Khi $D$ tăng lên, số cạnh có thể đi được chỉ tăng (không giảm), nên tính liên thông có tính đơn điệu: nếu $D$ hợp lệ thì mọi $D^{'} > D$ cũng hợp lệ.
Ta có thể tìm kiếm nhị phân trên $D$ trong khoảng $[0, 10^{9}]$ .
Để kiểm tra một giá trị $D$ : BFS/DFS từ điểm kiểm tra đầu tiên, chỉ đi qua các cạnh có chênh lệch $\leq D$ . Kiểm tra xem tất cả các điểm kiểm tra có đạt được không.

Thuật toán

Tìm kiếm nhị phân trên $D$ với $l o = 0$ , $h i = 10^{9}$ .
Với mỗi D cần kiểm tra:
- Tìm một điểm kiểm tra bất kỳ làm nguồn.
- BFS/DFS trên lưới $M \times N$ , mỗi bước chỉ sang ô kề có $| h_{u} - h_{v} | \leq D$ .
- Đếm số điểm kiểm tra đạt được. Nếu bằng tổng số điểm kiểm tra → hợp lệ.
Trả về $D$ nhỏ nhất hợp lệ.

Độ phức tạp

Thời gian: $O (M N \log (max h))$
Bộ nhớ: $O (M N)$

Bình luận

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