CCCHK '15 S3 - Symmetric Cross

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 3.0s
Memory limit: 256M

Problem types

You are given an R \times C matrix M. Each of its elements is either 0 or 1.

A cross of size k is a subregion of M, centering at one of its elements, containing the center and k elements in each of the four orthogonal directions (i.e., horizontal and vertical directions).

A cross is called "symmetric" if it does not change after being rotated by 90 degrees. Please find the cross with the largest size in M. It is guaranteed that there is exactly one such cross.

Input Specification

The first line contains two integers R and C, the number of rows and columns of M. The next R lines each contain C numbers separated by one space, representing M.

  • In 50\% of the test cases, 3 \le R,C \le 500.
  • In 100\% of the test cases, 3 \le R,C \le 2000.

Output Specification

The output contains a single line with three integers: the size of the largest symmetric cross in M, and the row and column number of its center.

Sample Input 1

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

Sample Output 1

2 3 3

Sample Input 2

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

Sample Output 2

1 2 2

Comments