Problem Description

You are given an $n \times m$ grid, where each cell has a color: black or white.

You can perform several operations. In one operation, you need to choose one direction from up, down, left, and right. Then, for every black cell, if the corresponding cell in the chosen direction is not outside the boundary of the grid, that corresponding cell becomes black.

Find the minimum number of operations needed so that any two black cells are 8-connected. The definition of 8-connectivity can be found in the [Hint/Notes] section.

Input Format

The first line contains two integers $n, m$ ($1 \leq n, m \leq 10^3$), representing the size of the grid.
The next $n$ lines each contain a 01 string of length $m$. If the $j$-th character of the $i$-th string is $1$, then the cell at row $i$ and column $j$ is black; otherwise, it is white.

Output Format

Output one integer in one line, the minimum number of operations.

5 4
1100
1000
0011
0000
0001

1

8 10
0000000011
0000000000
0000000000
0000000010
0000000000
0001010100
0000000000
0001000100

3

Hint

[Sample Explanation #1]

For the first sample, the initial grid is shown in Figure (1).

(1)

Perform one operation and choose the down direction. The grid becomes as shown in Figure (2) (the newly blackened cells are marked in red). At this point, any two black cells are 8-connected.

(2)

[Constraints]

This problem uses bundled testdata.

• Subtask 1 ($10$ points): $n, m \leq 3$.
• Subtask 2 ($10$ points): $n, m \leq 80$.
• Subtask 3 ($5$ points): the number of black cells does not exceed $20$.
• Subtask 4 ($5$ points): $m = 1$.
• Subtask 5 ($25$ points): $n, m \leq 300$.
• Subtask 6 ($45$ points): no special constraints.

For $100\%$ of the testdata, $1 \leq n, m \leq 10^3$ is guaranteed, and there is at least one black cell.

Definition of 8-connectivity

Two black cells are 8-connected if and only if they share a common vertex or a common edge, or there exists a black cell that is 8-connected to both of them.

In simpler terms, they can reach each other by moving only to the surrounding 8 adjacent cells, and only moving through black cells.

Translated by ChatGPT 5