Problem ID:
bomb
Points:
1.8 (partial)
Time limit:
1.0s
Memory limit:
125M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Trong thế chiến thứ hai, quân Đức Quốc xã đã lên kế hoạch ném bom một thành phố dựa vào bản đồ mà chúng thu thập được. Bản đồ thành phố có dạng một bảng ô vuông có kích thước ~N*M~, trong đó mỗi ô ở vị trí dòng ~i~, cột ~j~ (~1 \leq i \leq N, 1 \leq j \leq M~) được biểu diễn bởi các giá trị ~0/1~.
- Những ô có giá trị ~0~ biểu thị ở vị trí đấy là một khu đất trống.
- Những ô có giá trị ~1~ biểu thị ở vị trí đấy là một toà nhà.
- Mỗi khi quân Đức ném bom vào một toà nhà, thì toà nhà đó sẽ nổ.
- Khi một toà nhà nổ, thì nó sẽ làm nổ tất cả toà nhà nằm kề cạnh với toà nhà đó.
- Mỗi khi quân Đức ném bom vào một khu đất trống, không có gì xảy ra.
Hãy tìm số lần ném bom ít nhất để quân Đức có thể làm nổ tung tất cả toà nhà trong thành phố.
Dữ liệu vào
- Dòng thứ nhất ghi hai số nguyên ~N, M~ (~1 \leq N, M \leq 2000~).
- ~N~ dòng tiếp theo, dòng thứ ~i~ ghi một xâu nhị phân độ dài ~M~ mô tả hàng thứ ~i~ của bản đồ.
Dữ liệu ra
Một dòng duy nhất ghi số lần ném bom ít nhất có thể của quân Đức.
Sample Input
5 5
10011
10110
11001
00011
11001
Sample Output
4
Giải thích
Quân Đức có thể ném vào các toà nhà ở các vị trí ~(1, 1)~, ~(1, 5)~, ~(5, 1)~, ~(5, 5)~. Ta không thể tìm được phương án nào ném ít bom hơn nên ~4~ là đáp án tối ưu.
Comments