Dấu cộng lớn nhất
Đề bài
Mô tả
Tiến sĩ Memphis đang viết một chương trình nhận dạng dấu cộng ('+') trong một ảnh xám dạng bitmap. Chương trình của ông có thể nhận ra dấu cộng có dạng như sau:
- Dấu cộng được tạo thành từ các điểm ảnh đen kề nhau.
- Dấu cộng có kích thước với : tâm của nó có thể nằm ở một điểm ảnh bất kỳ, từ tâm kéo dài ra bốn hướng (lên, xuống, trái, phải), mỗi hướng gồm điểm ảnh. Nói cách khác, dấu cộng gồm điểm ảnh tâm và điểm ảnh liên tiếp theo mỗi hướng, tất cả đều là điểm ảnh đen.
Vì ảnh không rõ nét và có nhiễu, Tiến sĩ Memphis muốn tìm dấu cộng lớn nhất trong ảnh.
Yêu cầu: Cho một ảnh kích thước gồm các điểm ảnh đen và trắng. Hãy tìm dấu cộng lớn nhất trong ảnh.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên , : kích thước của ảnh.
- Mỗi dòng trong dòng tiếp theo chứa một xâu gồm ký tự '0' hoặc '1': '0' là điểm ảnh trắng, '1' là điểm ảnh đen.
Các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải.
Dữ liệu ra
- Dòng đầu tiên in kích thước của dấu cộng lớn nhất. Nếu ảnh không chứa dấu cộng nào, in ra -1.
- Nếu có dấu cộng, dòng thứ hai in hai số nguyên là chỉ số hàng và chỉ số cột của tâm dấu cộng lớn nhất. Nếu có nhiều dấu cộng lớn nhất, in dấu cộng có chỉ số hàng nhỏ nhất, nếu vẫn còn nhiều thì in dấu cộng có chỉ số cột nhỏ nhất.
Ràng buộc
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 8 00001000 00001000 00111110 00001000 00001000 00100000 01110000 00100000 |
9 3 5 |
Dấu cộng tâm với có kích thước . Dấu cộng tâm chỉ có . |
| 3 5 00000 00000 00000 |
-1 | Ảnh không có điểm ảnh đen nào. |
Bình luận