多源BFS AcWing 173. 矩阵距离

题意：

思路:将所有位置为1的点全部入队，然后进行BFS，确保每个点只搜索一次，时间复杂O(n*m)。当每个点向外扩展时，它能到达的点必须是最接近当前点的点，因此它必须能够确保曼哈顿从每个位置不到1的点到图中位置为1的点的最小距离。

#include #include #include using namespace std; const int N=1e3 10,INF=0x3f3f3f3f; int n,m; int d[N][N]; int dx[]={0，0，1，-1}，dy[]={1,-1,0,0}; struct node {     int x,y;     int s; }; queue q; void bfs() {     while(!q.empty())     {         node t=q.front();         q.pop();         int x=t.x,y=t.y,s=t.s;         d[x][y]=s;         for(int i=0;i<4;i  )         {             int tx=x dx[i],ty=y dy[i];             if(tx>=0&&tx=0&&tys 1)                 {                     d[tx][ty]=s 1;                     q.push({tx,ty,s 1});                 }             }         }     } } int main() {     scanf("%d%d",&n,&m);     int x;     memset(d,INF,sizeof(d));     for(int i=0;i