Days to Fill Garden

You are given a garden represented as a 2D grid with R rows and C columns. Each cell of the grid contains either a 0 or a 1. A value of 1 indicates that a flower is present and a 0 indicates an empty cell. Every day, each flower spreads to its adjacent cells (up, down, left, right), but not diagonally.

Your task is to determine the minimum number of days required to fill the whole garden with flowers. If it is impossible to fill the entire garden, output -1.

Mathematically, if we denote the garden as a matrix \(G\) with indices \(i\) and \(j\), then every day the update is given by: $$ G_{i,j}^{(d+1)} = \begin{cases} 1, & \text{if } G_{i,j}^{(d)} = 1 \text{ or any neighbor } G_{i\pm1,j}^{(d)} = 1 \text{ or } G_{i,j\pm1}^{(d)} = 1, \\ 0, & \text{otherwise.} \end{cases} $$

If the garden is already completely filled with flowers, the required number of days is 0.

inputFormat

The first line contains two integers R and C (1 ≤ R, C ≤ 10^3), representing the number of rows and columns of the garden. This is followed by R lines, each containing C space-separated integers (either 0 or 1), representing the garden grid.

outputFormat

Output a single integer indicating the minimum number of days required to fill the garden with flowers. If it is impossible to fill the garden, output -1.## sample

3 3
1 0 0
0 0 0
0 0 0

4