Nguồn: http://codeforces.com/
Bản đồ
của vùng Berland có kích thước n x m, trong đó mỗi ô vuông
đơn vị 1 x 1 là 1 trong 2 địa hình đất hoặc nước.
Một
vùng trên bản đồ được gọi là hồ khi nó là tập hợp các ô thỏa mãn các điều kiện:
1. Các
ô đều là nước
2. Có
thể di chuyển giữa hai ô bất kỳ trong hồ biết rằng từ 1 ô chỉ đi đến tối đa 4 ô
chung cạnh với nó và các ô đều phải là nước.
3.
Không có ô nào nằm trên cạnh của bản đồ.
Nhiệm vụ
của bạn là chọn ra ít nhất các ô nước để đổ đầy đất sao cho số lượng hồ còn lại
đúng bằng k, biết rằng số lượng hồ trong bản đồ ban đầu không nhỏ hơn k.
Dữ liệu vào: từ tệp văn bản
LAKES.INP
+ Dòng
đầu tiên chứa 3 số nguyên dương n, m, k (1≤n, m≤50; 0≤k≤50)
+ n
dòng tiếp theo, mỗi dòng chứa m ký tự, mỗi ký tự tượng trưng cho một
ô trong bản đồ, nếu ký tự là ‘.’ thì ô đó là nước, nếu kỳ tự là ‘*’ thì ô đó là
đất.
Dữ liệu ra: ghi vào tệp văn bản LAKES.OUT
+ Dòng
đầu là số nguyên duy nhất cho biết số lượng ít nhất các ô cần phải chuyển từ nước
thành đất.
+Các
dòng tiếp theo cho biết bản đồ sau khi chuyển một số ô nước thành đất
Ví dụ:
|
LAKES.INP
|
LAKES.OUT
|
|
5 4 1
**** *..* **** **.* ..** |
1
**** *..* **** **** ..** |
Solution:
Sử dụng DFS hoặc BFS để tìm số lượng thành phần liên thông (các vùng nước) trong bản đồ. Với mỗi thành phần liên thông cần lưu lại thông tin
1. Số lượng các ô
2. Tọa độ của 1 ô bất kỳ
Lưu ý thành phần liên thông không nằm ở biên của bản đồ (theo yêu cầu bài toán)
Giả sử ta có top thành phần liên thông
Sắp xếp các thành phần liên thông theo chiều tăng dần của số lượng các ô.
Kết quả là tổng của bài toán là tổng các ô của top-k thành phần liên thông đầu tiên (đã sắp xếp)
Trong top-k thành phần liên thông đầu tiên ta duyệt lại dựa vào tọa độ của 1 ô trong mỗi thành phần liên thông để thay dấu '.' thành dấu '*'.
