Largest Plus-Shaped Flower Bed

A gardener has an n by n plot, with rows and columns numbered from 0. Every square is good soil except for some rocks, given as a list rocks of [row, col] pairs. She wants to plant the largest plus-shaped flower bed that fits.

A plus of size k is centred on one square and has four arms, going up, down, left and right from the centre, each k - 1 squares long. All 4 * (k - 1) + 1 of its squares must be soil and inside the plot; the squares between the arms do not matter. A single soil square is a plus of size 1.

Write largest_plus(n, rocks) that returns the size of the largest plus that fits, or 0 if every square is a rock.

Examples

largest_plus(5, [[1, 1], [3, 3]])         # returns 3
largest_plus(5, [[0, 2]])                 # returns 2
largest_plus(2, [[0, 0], [1, 1]])         # returns 1
largest_plus(1, [[0, 0]])                 # returns 0

In the first example the rocks sit between the arms, so the size 3 plus centred on (2, 2) fits. In the second, the rock at the top of the middle column cuts that plus short, and only size 2 is left.

Constraints

• 1 <= n <= 300.
• 0 to 90,000 rocks, all inside the plot; a rock may be listed more than once.