题目描述
古老的显示屏是由N×M个像素（Pixel）点组成的。一个像素点的位置是根据所在行数和列数决定的。例如P(2,1)表示第2行第1列的像素点。那时候，屏幕只能显示黑与白两种颜色，人们用二进制0和1来表示。0表示黑色，1表示白色。当计算机发出一个指令：P(x,y)=1，则屏幕上的第x行第y列的阴极射线管就开始工作，使该像素点显示白色，若P(x,y)=0，则对应位置的阴极射线管不工作，像素点保持黑色。在某一单位时刻，计算机以N×M二维01矩阵的方式发出显示整个屏幕图像的命令。
例如，屏幕是由3×4的 对应屏幕显示应为：像素点组成，在某单位时刻，计算机发出如下命令：
0001 0011 0110
假设放大后，一个格子表示一个像素点
由于未知的原因，显示黑色的像素点总是受显示白色的像素点的影响——可能是阴极射线管工作的作用。并且，距离越近，影响越大。这里的距离定义如下：设有像素点P1(x1,y1)和像素点P2(x2,y2)，则它们之间的距离D(P1,P2)：D(P1,P2)=|x1-x2|+|y1-y2| 在某一时刻，计算机发出显示命令后，科学家们期望知道，每个像素点和其最近的显示白色的像素点之间的最短距离是多少——科学家们保证屏幕上至少有一个显示白色的像素点。
上面的例子中，像素P(1,1)与最近的白色像素点之间的距离为3，而像素P(3,2)本身显示白色，所以最短距离为0。
输入格式
第一行有两个数字，N和M (1<=N,M<=182)，表示屏幕的规格。
以下N行，每行M个数字，0或1。为计算机发出的显示命令。
输出格式
输出文件有N行，每行M个数字，中间用1个空格分开。第i行第j列的数字表示距像素点P(i,j)最近的白色像素点的最短距离。
输入输出样例
输入 #1复制
3 4
0001
0011
0110
输出 #1复制
3 2 1 0
2 1 0 0
1 0 0 1
说明/提示
对于30%的数据：NM<=10000；
对于100%的数据：NM<=182^2。

算法1

(多源BFS) $O(n*m)$

和距离矩阵那题一模一样，只不过换了一个说法而已
由于bfs每次是一层一层拓展，新的点到原点一定是距离最小的，抓住1往四个方向看

C++ 代码

#include<iostream>
using namespace std;
const int N = 1010,M = N * N;
int n,m;
char g[N][N];
int dist[N][N];

typedef pair<int,int> PII;
#define x first
#define y second
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
bool st[N][N];
void bfs()
{
    int hh = 0,tt = 0;
    PII q[M];
    for(int i = 0 ; i < n; i++)
        for(int j = 0 ; j < m; j++)
        {
            if(g[i][j] == '1')
            {
                st[i][j] = true;
                q[tt++] = {i,j};
            }
        }
    while(hh <= tt)
    {
        PII t = q[hh++];
        for(int i = 0 ; i < 4; i++)
        {
            int a = t.x + dx[i] ,b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m)continue;
            if(g[a][b] == '1')continue;
            if(st[a][b])continue;
            dist[a][b] = dist[t.x][t.y] + 1;
            q[tt++] = {a,b};
            st[a][b] = true;
        }
    }

}
int main()
{
    cin >> n >> m;
    for(int i = 0 ; i < n; i++) cin >> g[i];
    bfs();
    for(int i = 0 ; i < n; i++)
    {
        for(int j = 0 ; j < m; j++)
        {
            cout << dist[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}