Bài 24.3. Mẫu Vết Thập Tự Lớn Nhất - [Độ khó: Khó]

Trong một dự án nghiên cứu thiên văn, các nhà khoa học đang phân tích dữ liệu từ một kính viễn vọng không gian, biểu diễn dưới dạng một ma trận nhị phân. Các ô có giá trị '1' biểu thị tín hiệu thiên văn mạnh, còn '0' là nhiễu. Họ đặc biệt quan tâm đến việc xác định các "vết thập tự" (Cross patterns) của tín hiệu. Một vết thập tự có kích thước k được định nghĩa bởi một ô trung tâm (r, c) có giá trị '1', và k ô liên tiếp có giá trị '1' mở rộng ra từ ô trung tâm theo bốn hướng chính (lên, xuống, trái, phải). Tất cả các ô tham gia vào vết thập tự đều phải có giá trị '1'. Kích thước k là độ dài của mỗi cánh tay, không tính ô trung tâm. Ví dụ, một vết thập tự kích thước k=0 chỉ là một ô '1' đơn lẻ. Vết thập tự kích thước k=1 sẽ có dạng:

  1
1 1 1
  1

Nhiệm vụ của bạn là tìm kích thước k lớn nhất của một vết thập tự có thể tìm thấy trong ma trận tín hiệu.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên dương N và M (3 <= N, M <= 500), lần lượt là số hàng và số cột của ma trận tín hiệu. N dòng tiếp theo, mỗi dòng chứa M số nguyên A[i][j] (0 hoặc 1), biểu diễn giá trị tín hiệu tại từng ô.

OUTPUT FORMAT

In ra một số nguyên duy nhất là kích thước k lớn nhất của vết thập tự tìm được. Nếu không có bất kỳ ô '1' nào, in ra 0.

Ví dụ:

Input:

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

Output:

1

Giải thích:

• Ma trận đã cho:

  0 0 0 0 0
  0 0 1 0 0
  0 1 1 1 0
  0 0 1 0 0
  0 0 0 0 0

• Duy nhất ô (2,2) là trung tâm của một vết thập tự.
• Kiểm tra ô (2,2):
  • Nó là '1'.
  • Cánh tay lên: (1,2) là '1'. Có thể kéo dài 1 ô.
  • Cánh tay xuống: (3,2) là '1'. Có thể kéo dài 1 ô.
  • Cánh tay trái: (2,1) là '1'. Có thể kéo dài 1 ô.
  • Cánh tay phải: (2,3) là '1'. Có thể kéo dài 1 ô.
• Vì tất cả 4 cánh tay đều có thể kéo dài ít nhất 1 ô, ô (2,2) có thể là trung tâm của một vết thập tự kích thước k=1.
• Không thể tìm thấy vết thập tự kích thước k=2 vì ví dụ (0,2) (lên trên từ (1,2)) là 0, (4,2) (xuống dưới từ (3,2)) là 0, v.v.
• Do đó, kích thước k lớn nhất là 1.

Ví dụ 2:

Input:

7 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0

Output:

2

Giải thích:

• Vết thập tự lớn nhất có tâm tại (3,3).
• Các cánh tay có thể mở rộng 2 ô lên, xuống, trái, phải.
  • Lên: (2,3) (1), (1,3) (1)
  • Xuống: (4,3) (1), (5,3) (1)
  • Trái: (3,2) (1), (3,1) (1)
  • Phải: (3,4) (1), (3,5) (1)
• Do đó, kích thước k lớn nhất là 2.