The Largest Plus Sign
A PLUS SIGN of order k centred at a cell consists of that cell plus four arms of
k - 1 cells each, going up, down, left and right. Every cell of the plus must be a 1 and
must lie inside the grid.
Print the largest order of any plus sign, or 0 if the grid has no 1 at all.
0 1 0
1 1 1 -> 2 centred at the middle cell, arms of length 1
0 1 0
## Why the corner trick does not apply
Problems 534 and 536 anchor a square at its bottom-right corner and grow it with a single recurrence. A plus sign has no corner: it grows in FOUR directions from a centre, and the four are independent.
So the state is not one number built from neighbours. It is four numbers, one per direction, and the plus's order is their minimum.
## Four directional runs
For each cell, compute how many consecutive 1s end at it in each of the four directions:
left[r][c] running along the row, left to right
right[r][c] running along the row, right to left
up[r][c] running down the column
down[r][c] running up the column
Each is a single pass with a counter that increments on a 1 and resets to 0 on a 0, which
is the same running-length idea as problem 475.
The order of the largest plus centred at a cell is
min( left, right, up, down )
and the answer is the maximum of that over all cells.
## Why a minimum of four
An arm of length k - 1 must exist in every direction, so the plus is limited by the
SHORTEST run. Taking the maximum instead reports pluses with missing arms.
The centre is counted in all four runs, which is why the minimum is the ORDER directly and
needs no adjustment. A cell that is a 1 with no room in any direction has all four runs
equal to 1, giving order 1, which is correct: a single cell is a plus of order 1.
## Collapsing four tables into one
All four passes write into the same array, each taking a minimum with what is there:
dp[r][c] = INFINITY initially
each of the four sweeps does dp[r][c] = min(dp[r][c], run)
That keeps the memory at one grid instead of four, and it makes the "minimum of four" step disappear into the sweeps. Recognising that several tables which are only ever combined by one associative operation can share storage is worth more than this problem.
## Boundaries
A 2 by 2 grid of all ones answers 1: no cell has room for an arm in every direction, since each is on two borders.
A 3 by 3 of all ones answers 2 and a 5 by 5 answers 3. The pattern is that a grid of side
s filled with ones has order (s + 1) / 2 rounded down, which is worth checking against
those three.
An all-zero grid answers 0.
## Cost
Time O(m n), four sweeps. Space O(m n).