题目链接：https://www.acwing.com/problem/content/175/
题目给出一个01矩阵，要求对于每个点给出图中一个为1的点到这个位置的曼哈顿距离，要求这个曼哈顿距离最小。
转化成多源搜索，对于每一个1，扔进队列进行扩展，扩展到一个没访问过的点一定是到这个点的最短的曼哈顿距离，因为bfs是层次性的扩展，一旦扩展到就一定是最短的。
当然，最初的时候为1的点step都是0，并且都入队开展层次为1的扩展。
代码：
#include<iostream> #include<cstdio> #include<queue> using namespace std; #define maxn 1010 char s[maxn][maxn]; int d[maxn][maxn]; bool vis[maxn][maxn]; int n,m; struct node{ int x,y,step; }; queue<node> q; node cur,nxt; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; void bfs(){ while(!q.empty()){ cur=q.front(); q.pop(); for(int i=0;i<4;i++){ nxt.x=cur.x+dx[i]; nxt.y=cur.y+dy[i]; nxt.step=cur.step+1; if(nxt.x<0 || nxt.x>n || nxt.y<0 || nxt.y>m)continue; if(vis[nxt.x][nxt.y])continue; vis[nxt.x][nxt.y]=1; d[nxt.x][nxt.y]=nxt.step; q.push(nxt); } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++)scanf("%s",s[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(s[i][j]=='1'){ vis[i][j]=1; d[i][j]=0; q.push(node{i,j,0}); } } bfs(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)printf("%d ",d[i][j]); puts(""); } }