Submit solution
Points:
250.00
Time limit:
1.0s
Memory limit:
100M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Năm 21XX, một cuộc khủng hoảng năng lượng nổ ra, quốc vương A quyết định cử một đội máy thăm dò lên sao Hỏa để tìm kiếm dầu mỏ. Đội thăm dò sẽ thăm dò trên một mảnh đất chia làm ~M*N~ ô bằng các máy thăm dò, mỗi máy thăm dò sẽ chiếm một ô vuông ~k*k~ và thăm dò trên diện tích mà nó chiếm, máy thăm dò có thể di chuyển sang các ô kề cạnh, khi thăm dò xong máy lập tức trở về (vì sợ hết nhiên liệu) chứ không nhảy sang các khu vực khác. Nhưng điều này là khó khó khăn đối với đội thăm dò.
Bạn hãy giúp họ đưa ra số máy thăm dò ít nhất sao cho tất cả các khu đất hình vuông ~k*k~ đều được thăm dò.
![](http://oj.lequydon.net/media/martor/7740ccf8-ce1c-4430-a11d-050092b87b78.png)
Input:
- Dòng đầu chứa 3 số ~M~, ~N~, ~K~ mỗi số cách nhau một dấu cách, 0 < ~M,N~ ≤ 1000; 0 < ~k~ < ~min(M,N)~;
- ~M~ dòng sau, mỗi dòng gồm ~N~ số, 0 biểu thị cho đất, 1 biểu thị cho đá không được đi qua.
Output: Gồm 1 số duy nhất ghi số lượng máy cần cử đi.
Ví dụ
Input
4 8 3
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output
2
Giới hạn: Có ít nhất 60% số test ứng với ~M,N~<=100.
Comments