一.题目链接：

矩阵距离

二.题目大意：

给你一个 n × m 的 01 矩阵 A，现求矩阵 B.

三.分析：

每个点 BFS 肯定会 T.

一开始想的是从 （1,1）开始搜，记一下曼哈顿距离，之后二分查找做差，写完之后发现思路根本不对。。。

正解是把每个 1 在一开始加到队列里去，然后 BFS 即可. （wsl）

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;

const int M = (int)1e3;
const int mod = 99991;
const int inf = 0x3f3f3f3f;

int n, m;
char s[M + 5][M + 5];
int step[M + 5][M + 5];
pair <int, int> p, t;
queue < pair<int, int> > q;
int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};

void bfs()
{
    memset(step, -1, sizeof(step));
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(s[i][j] == '1')
            {
                step[i][j] = 0;
                p.first = i, p.second = j;
                q.push(p);
            }
        }
    }
    while(!q.empty())
    {
        p = q.front(), q.pop();
        for(int i = 0; i < 4; ++i)
        {
            t = p;
            t.first += dx[i], t.second += dy[i];
            if(t.first >= 1 && t.first <= n && t.second >= 1 && t.second <= m && step[t.first][t.second] == -1)
            {
                step[t.first][t.second] = step[p.first][p.second] + 1;
                q.push(t);
            }
        }
    }
}

/**
2 2
00
11

**/

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i)
        scanf("%s", s[i] + 1);
    bfs();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            printf("%d%c", step[i][j], j == m ? '\n' : ' ');
    return 0;
}