Largest plus bed: hints, no solution
Medium · 2-D dynamic programming
A garden plan is a list of equal-length strings, one per row, where '.' is a free bed and '#' is a blocked cell. A plus-shaped bed has a free centre cell and four arms of the same length a (a can be 0) reaching up, down, left and right from the centre. Every cell of the plus must be free and inside the grid, and the plus covers 4a + 1 cells. Return the number of cells of the largest plus that fits, or 0 if the plan has no free cell at all.
Examples
- Input
- beds = ["...", "...", "..."]
- Output
- 5
- Note
- The centre cell has arms of length 1 in every direction.
- Input
- beds = ["##", "##"]
- Output
- 0
- Note
- Every cell is blocked.
- Input
- beds = [".....", "..#..", ".....", "....."]
- Output
- 5
- Note
- The blocked cell shortens the plus centred nearby.
Constraints
- 0 <= beds.length <= 150, and all rows have the same length between 1 and 150
- Each character is '.' or '#'
Hint 1: a nudge
Pick a possible centre cell. What decides how long its four arms can be, and can they differ in length?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.