Dấu cộng toàn số 1 lớn nhất

Bối cảnh

Trong một bản đồ nhị phân, ô có giá trị 1 là vùng có tín hiệu, ô 0 là vùng trống. Một dấu cộng hợp lệ có một tâm (i,j) bằng 1 và bốn cánh kéo dài cùng số bước k theo bốn hướng trên, dưới, trái, phải; mọi ô trên cả bốn cánh từ tâm ra đến khoảng cách k đều phải bằng 1. Ta định nghĩa armLength = k+1, tức dấu cộng chỉ có tâm thì armLength=1, thêm một lớp bốn phía thì armLength=2,...

Hãy tìm dấu cộng có armLength lớn nhất. Nếu có nhiều dấu cộng cùng kích thước, chọn tâm theo thứ tự hàng nhỏ hơn rồi cột nhỏ hơn. Nếu ma trận không có ô 1, in 0 -1 -1.

Bài Hard buộc người làm kiểm soát biên, tính liên tục của cánh và điều kiện "cả bốn hướng cùng mở rộng". Không có DP hay prefix 2D trong prerequisite, nên lời giải chuẩn sử dụng mở rộng trực tiếp từ từng tâm.

Điểm khác biệt với kiểm tra 5 ô là dấu cộng có thể có nhiều lớp. Khi mở rộng tới lớp k, nếu một trong bốn ô mới bằng 0 hoặc vượt biên thì không thể mở rộng thêm nữa.

Yêu cầu

1. Duyệt mọi ô 1 làm tâm ứng viên.
2. Tâm tự tạo armLength=1.
3. Tăng k từ 1; ở mỗi lớp kiểm tra bốn ô ở khoảng cách k. Nếu tất cả là 1 thì cập nhật kích thước; nếu không thì dừng tâm đó.
4. Giữ tâm đầu tiên khi tie.

Input

Dòng 1: rows cols; sau đó ma trận chỉ gồm 0 và 1.

Output

Một dòng maxArmLength row col; nếu không có ô 1 thì 0 -1 -1.

Ràng buộc

1 ≤ rows,cols ≤ 100, mỗi ô là 0 hoặc 1.

Ví dụ 1

Input

5 5
0 0 1 0 0
0 0 1 0 0
1 1 1 1 1
0 0 1 0 0
0 0 1 0 0

Output

3 2 2

Giải thích

Ma trận tạo đúng một dấu cộng lớn tâm tại (2,2): từ tâm có thể mở rộng 2 ô theo cả bốn hướng và tất cả các ô cần thiết đều bằng 1. Với radius 2, độ dài cánh theo quy ước bài là k+1 = 3 (tâm cộng hai ô trên mỗi hướng). Mọi tâm khác bị giới hạn bởi biên hoặc gặp 0 sớm hơn, nên dấu cộng lớn nhất có arm length 3 tại (2,2). Output là 3 2 2.

Ví dụ 2

Input

3 3
0 0 0
0 0 0
0 0 0

Output

0 -1 -1

Giải thích

Toàn bộ ma trận đều bằng 0 nên không có ô nào đủ điều kiện làm tâm, ngay cả với cánh ngắn nhất. Biến đáp án không bao giờ được cập nhật từ trạng thái "không có dấu cộng". Vì vậy chương trình in bộ giá trị đặc biệt 0 -1 -1.

Thông tin học tập

• Module: M03
• Buổi: B11
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: 2D static arrays, binary matrix, expanding cross, brute force, geometry, tie-break
• Giới hạn kiến thức: B01-B11
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100