trang chủ / đề bài / icpc21_mn_j

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 4×k+1 với k≥0: 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 k điểm ảnh. Nói cách khác, dấu cộng gồm điểm ảnh tâm và k đ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 m×n 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 m, n: kích thước của ảnh.
  • Mỗi dòng trong m dòng tiếp theo chứa một xâu gồm n 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ừ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến 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

  • 1≤m,n≤5000.

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 (3,5) với k=2 có kích thước 9. Dấu cộng tâm (7,2) chỉ có k=1.
3 5
00000
00000
00000
-1 Ảnh không có điểm ảnh đen nào.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0