矩阵距离

链接：https://ac.nowcoder.com/acm/problem/51024
来源：牛客网

给定一个N行M列的01矩阵 A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：
dist(A[i][j],A[k][l]) =|i-k|+|j-l|
输出一个N行M列的整数矩阵B，其中：
B[i][j]=min(1\leq x\leq N,1\leq y\leq M,A[x][y]=1)B[i][j]=min(1≤x≤N,1≤y≤M,A[x][y]=1)⁡{dist(A[i][j],A[x][y])}
即求与每个位置曼哈顿距离最近的1
N,M \leq 1000N,M≤1000

输入描述:
第一行两个整数n,m。
接下来一个N行M列的01矩阵，数字之间没有空格。
输出描述:
一个N行M列的矩阵B，相邻两个整数之间用一个空格隔开。

曼哈顿距离这里这也只是从1到0要走的距离
然后就是bfs直接套，但我以前做的都是从一个点找另一个点，但这个是从一群1找0，相当于初始化时初始了一大堆

//https://ac.nowcoder.com/acm/problem/51024
#include<bits/stdc++.h>
#define ll long long  
using namespace std;
const int N=1010; 
//#define ll long long
typedef pair<int,int>PII;
//vector<PII> q;
int n,m,k,sum=0,cet=0,keyy=0,d[N][N]; 
//int d[N][N],kk[N][N];
char a[N][N];
//priority_queue<int>q;
queue<PII>q;
void bfs()
{
    int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
    while(q.size())
    {
        auto t=q.front();
        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i],y=t.second+dy[i];
            if(x<0||x>=n||y<0||y>=m||d[x][y]!=-1) continue;
            q.push({x,y});
            d[x][y]=d[t.first][t.second]+1;    
        }
        q.pop();
    }
}
int main()
{    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    memset(d,-1,sizeof d);
    for(int i=0;i<n;i++)
        for(int k=0;k<m;k++)
        {
            cin>>a[i][k];
            if(a[i][k]=='1') d[i][k]=0,q.push({i,k});//相当于初始化，因为1有好多个
            //然后从每一个1开始向外走，最终达到遍历每一个0 
        }
    bfs();
    for(int i=0;i<n;i++)
    {
        for(int k=0;k<m;k++) cout<<d[i][k]<<" ";
        cout<<endl;
    }

    return 0;
}