P2335 [SDOI2005] Bitmap

You are given a monochrome bitmap of size $n\ \times m$, which contains at least one white pixel. We use $(i,j)$ to denote the pixel in the $i$-th row and $j$-th column, and define the distance between two points $p_1=(i_1,j_1)$ and $p_2=(i_2,j_2)$ as: $$d(p_1,p_2)=|i_1-i_2|+|j_1-j_2|.$$ Your task is to read the bitmap and, for each pixel, compute the distance to the nearest white pixel. Output the result.

The first line contains two space-separated integers $n$ and $m$, where $1 \le n \le 150$ and $1 \le m \le 150$. Each of the next $n$ lines contains a string of length $m$ consisting of characters '0' and '1'. In the $i$-th of these lines, if the $j$-th character is '1', then pixel $(i,j)$ is white; otherwise it is black.

Output an $n\ \times m$ table of numbers. In this table, the $j$-th number in the $i$-th row is $f(i,j)$, which denotes the distance from pixel $(i,j)$ to its nearest white pixel.

Translated by ChatGPT 5