You are given a matrix of integers matrix containing only zeros and ones.
Let’s call an x-shape a figure with a center at some cell of matrix and 4 diagonal rays of equal length. The x-shape is called perfect if all its elements equal 1.
For example, there is one perfect x-shaped figure of size 2 with a center at [1, 1], and five perfect x-shaped figures of size 1 in the following matrix:
[[1, 0, 1],
[0, 1, 0],
[1, 0, 1]]At the same time, the following matrix has only four perfect x-shaped figures of size 1:
[[1, 1],
[1, 1]]Return the center coordinates [row, col] of the largest perfect x-shaped figure within the matrix. If there are multiple answers, return the one with the smallest row value first, and if still tied, the smallest column value.
This problem asks for the center of the largest perfect X-shape in a binary matrix. The standard solution is to precompute, for every cell, how many consecutive 1s extend in each of the four diagonal directions, then take the minimum of those four values as the X-shape size centered there. Scanning all cells and applying the tie-breaking rule gives an O(nm) dynamic programming solution that is efficient and clean.
