Invader Jina

The planet is an $N$ by $M$ grid. Each cell is either empty ($0$) or a village ($1$). You must place exactly $2$ poison bags, each on an empty cell.

Every second, the poison spreads to the four neighboring cells (up, down, left, right). A poisoned village infects each adjacent village after $1$ second, so the spread is equivalent to movement through every cell of the grid. A village at $(x, y)$ becomes poisoned at the smaller of its Manhattan distances to the two bags, and the time to poison every village is the maximum of those values over all villages. Find the placement that minimizes this maximum.

Rows are numbered from $0$ to $N-1$ and columns from $0$ to $M-1$, with the top-left cell at $(0, 0)$. The input always admits a placement.

The first line contains two integers $N$ and $M$ separated by a space. ($2 \le N, M \le 20$)

Each of the following $N$ lines contains a string of length $M$. Each character is $0$ or $1$, where $0$ means an empty cell and $1$ means a village.

Print the minimum time in seconds needed to poison every village when the $2$ poison bags are placed on the best empty cells.