MARS - Chỉnh sửa ảnh
Giới hạn- Thời gian: 0.4s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Trung tâm của bạn vừa nhận được 1 bức ảnh chụp bề mặt sao Hỏa. Bức ảnh được mã hóa theo dạng hình chữ nhật được chia thành các ô vuông, trong đó mỗi ô có thể có màu đen hoặc trắng. Do nhiều lí do trên đường vận chuyển, có tối đa K ô bị mờ đi (đen thành trắng), nhưng do không thể xác định chính xác được ô nào bị mờ, nên bạn buộc phải giả sử rằng tất cả các khả năng mờ đi đều có thể xảy ra.
Để xác định các vật thể lạ trên sao Hỏa, trung tâm của bạn căn cứ theo các ô đen được chụp trên tấm ảnh. Hai ô đen A và B được gọi là cùng thuộc một vật thể, nếu từ A, tồn tại một đường đi thỏa mãn chỉ đi qua các ô đen kề cạnh, có thể đến được B. Kích thước vật thể được tính bằng khoảng cách Euclid của 2 ô xa nhau nhất cùng thuộc vật thể đó.
Yêu cầu: xác định kích thước lớn nhất có thể có được của 1 vật thể trên tấm ảnh.
Input
- Dòng đầu tiên chứa 3 số nguyên M,N,K (0 < M,N <= 50, 0 <= K <= M * N) là kích thước tấm ảnh và số ô tối đa đã bị mờ đi
- M dòng sau, mỗi dòng chứa N kí tự 0/1 tương ứng với ô đó có màu đen (0) hay trắng (1)
- Trong 20% số test, 0 < M,N <= 4
- Trong 60% số test, 0 < M,N <= 25
Output
- Đưa ra 1 số nguyên duy nhất là bình phương kích thước của vật thể lớn nhất
Example
Input: 4 4 0 0010 1001 0011 0111 Output: 10
(Không có ô nào được sửa. Có 2 vật thể, và kích thước của vật thể lớn hơn là khoảng cách giữa 2 ô được gạch chân)
Input: 4 4 4 0010 1001 0011 0111
Output: 18
(Nếu tô đen ô 1 được gạch chân, kích thước của vật thể sẽ là khoảng cách của 2 ô được gạch chân. Có thể tô đen nhiều hơn 1 ô, nhưng khoảng cách không thay đổi)
- Người up: voj
- Nguồn bài: Nguyễn Vương Linh