545. 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).

Constraints - `1 ≤ m ≤ 500` - `1 ≤ n ≤ 500` - every value is `0` or `1`