Chuột và khoai lang
View as PDF
Submit solution
Points:
200.00 (partial)
Time limit:
0.5s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Trong một mảnh vườn hình chữ nhật có kích thước M×N, người ta chia mảnh vườn thành M hàng và N cột, các hàng và cột tạo thành các ô đơn vị hình vuông có cạnh bằng 1, người ta trồng khoai lang trong những ô đơn vị hình vuông. Trong mảnh vườn này có một chú chuột ở trong hang, chú chuột này cần xác định miền (Hai miền khác nhau không có một cạnh ô vuông nào chung) người ta đã trồng khoai lang có diện tích lớn nhất trong mảnh vườn để đào một đường hầm đến phần diện tích lớn nhất đó. Hãy viết chương trình giúp chú chuột tìm được miền chứa khoai lang nhiều nhất.
Dữ liệu vào:
- Dòng đầu tiên ghi 2 số nguyên dương M và N là kích thước của mảnh vườn.
- Trong M dòng tiếp theo, mỗi dòng có N ký tự 0 hoặc 1, với ý nghĩa 0 là không trồng khoai lang, 1 là có trồng khoai lang
Giới hạn: 1≤M,N≤1000
Kết quả:Một số nguyên là tổng số dây khoai lang của miền có diện tích lớn nhất (giả sử mỗi ô chỉ có tối đa một dây khoai lang)
Ví dụ:
Input 1:
6 6
000111
000011
000011
000011
000011
111000
Output 1:
11
Comments
final
~Ame doko?