Vùng biển của Lulu

View as PDF

Submit solution

Points: 1.19 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Tranhu Thái Huy - C11 Contest Round 20
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Lulu là tên của một chú hải cẩu. Chú ta cai quản một vùng biển rộng. Vùng biển ấy bao gồm đảo ( phần cạn ), ao, hồ, các con sông ( phần nước trên đất liền) và biển xung quanh các đảo ( phần nước dưới biển). Để tiện việc quản lí, Lulu đã vẽ bản đồ cho vùng biển của mình. Bản đồ có thể xem như một ảnh hình chữ nhật có kích thước các cạnh là ~M~, ~N~ và bao gồm ~M*N~ bit trắng đen. Mỗi bit sẽ tương ứng với một mảnh đất đơn vị trên thực tế. Bit đen sẽ tượng trưng cho phần cạn và bit trắng sẽ tượng trưng cho phần nước.

Vùng biển của Lulu vừa mới được UNESCO công nhận là Di sản tự nhiên của Thế giới. Nên các nhà đầu tư ào ạt đổ tới đây để xây các Resort, khu nghỉ mát, nghỉ dưỡng, v.v... Họ sẽ mua những mảnh đất có hình chữ nhật . Và vì được sử dụng đế xây các khu du lịch biển, nên mảnh đất đó phải có cả phần nước và phần cạn . Họ gọi những mảnh đất như thế là những mảnh đất đẹp .

Sau khi biết điều này, Lulu sẽ bán các mảnh đất của mình như sau:

  • Các mảnh đất được bán phải nằm khít trên bản đồ.
  • Không chấp nhận việc chia nhỏ một mảnh đất đơn vị để bán.
  • Giá bán của một mảnh đất đơn vị là số mảnh đất đẹp mà nó nằm trên.
  • Giá bán của một mảnh đất bất kì là tổng giá bán của các mảnh đất đơn vị của nó.

Alex là một đại gia nổi tiếng trên thế giới. Anh ấy đã quyết định mua hết cả vùng biển ~M*N~ của Lulu. Việc khảo sát giá của 1 mảnh đất đơn vị hay 2 mảnh đất đơn vị hay 3 mảnh đất đơn vị là chuyện nhỏ đối với Lulu. Nhưng giờ đây lại phải cùng lúc khảo sát đến tất cả là ~M*N~ mảnh đất đơn vị, đó là một điều không thể nào kết thúc trong nháy mắt được.

Bây giờ bạn là người được thuê để tính toán hộ số tiền Alex phải trả.

Input

  • Dòng đầu tiên 2 số ~M~, ~N~ cho biết kích thước của vùng biển Lulu sở hữu.
  • ~M~ dòng sau, mỗi dòng một dãy gồm ~N~ bit (0 hoặc 1) cho biết bản đồ của vùng biển (0 là trắng, 1 là đen).

Output

  • Một số duy nhất là kết quả của bài toán.

Giới hạn

  • ~1~ ~\leq~ ~M~, ~N~ ~\leq~ ~2000~.
  • ~30\%~ số test có ~M~, ~N~ ~\leq~ ~20~.
  • ~50\%~ số test có ~M~, ~N~ ~\leq~ ~100~.

Sample Input

2 2
01
01

Sample Output

8

Comments

Please read the guidelines before commenting.


There are no comments at the moment.