Đàn kiến
Đề bài
Mô tả
Cho một bản đồ kích thước (), mỗi ô được điền ngẫu nhiên một số. Theo thời gian, một số tổ kiến xuất hiện trên bản đồ. Mỗi tổ kiến chiếm một ô của bản đồ và được biểu diễn bằng ký hiệu *. Số tổ kiến không quá . Ngoài ra, bản đồ luôn có ít nhất một ô không chứa ký hiệu *.
Ban đầu, giữa các tổ kiến không có quan hệ gì, mỗi tổ thuộc một loài kiến khác nhau. Một nhà nghiên cứu muốn hợp nhất tất cả các loài này thành một loài duy nhất. Ông dự định mỗi lần dẫn toàn bộ kiến của hai loài khác nhau tới một vị trí trên bản đồ không có tổ kiến nào để thực hiện việc hợp nhất. Kiến có thể di chuyển theo bốn hướng: lên, xuống, trái, phải, không được đi chéo. Chi phí di chuyển là tổng các số trên bản đồ dọc theo đường đi mà kiến đi tới vị trí mong muốn (tính cả ô đích, không tính ô xuất phát). Kiến đi vào tổ của mình hoặc tổ của loài khác thì không mất chi phí. Sau khi hai loài hợp nhất, tất cả kiến trở thành một loài duy nhất và có thể quay về các tổ ban đầu của mình mà không tốn thêm chi phí. Kiến của một loài xuất phát từ tất cả các tổ của loài đó: mỗi tổ đều phải đưa kiến của mình tới vị trí hợp nhất.
Hãy tính tổng chi phí nhỏ nhất để nhà nghiên cứu đạt được mục tiêu.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên ().
- dòng tiếp theo mô tả bản đồ, mỗi dòng gồm phần tử cách nhau bởi dấu cách; mỗi phần tử là một số nguyên dương (không vượt quá ) hoặc ký hiệu
*. Đảm bảo có ít nhất một ô không chứa ký hiệu*và có không quá ký hiệu*.
Dữ liệu ra
In ra tổng chi phí nhỏ nhất theo yêu cầu của đề bài.
Ràng buộc
- Mỗi số trên bản đồ là số nguyên dương không vượt quá .
- Số tổ kiến không quá ; có ít nhất một ô không có tổ kiến.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 5 6 10 3 * 4 3 3 * |
6 | Hai tổ kiến cùng đi tới ô để hợp nhất, mỗi tổ tốn . |
| 4 10 7 * 10 5 * 1 8 * 6 * 1 3 7 9 9 |
14 | Gọi các loài là A , B , C , D . A và B hợp nhất tại ô với chi phí , thành loài E. E (hai tổ) và D hợp nhất tại với chi phí , thành loài F. Cuối cùng C và F hợp nhất tại với chi phí (kiến loài C đi qua tổ B miễn phí). Tổng chi phí là . |
Bình luận