#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; int m,n; int pho[200][200]; int f[200][200]; int vis[200][200],looked; struct t{ int x,y,cost; }; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; queue <t> q; void bfs() { memset(f,0x3f,sizeof(f)); t p; while(!q.empty()) { p=q.front(); q.pop(); int x=p.x; int y=p.y; vis[x][y]++; int cost=p.cost; if(vis[x][y]>=looked*2) continue; //每个点在正常情况下会被访问最多n(looked)次，为了保险乘了2 if(f[x][y]<cost) continue; //类似于一个剪枝，记录在当前状态已经做过一次比他更优的计算（cost为当前距离，f标记每个点最小距离） f[x][y]=cost; for(int i=0;i<=3;i++) { if(x+dx[i]<=n&&x+dx[i]>=1&&y+dy[i]<=m&&y+dy[i]>=1) { t a; a.x=x+dx[i]; a.y=y+dy[i]; a.cost=cost+1; q.push(a); } } } return ; } int main() { scanf("%d %d",&n,&m); int i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%d",&pho[i][j]); t b; b.x=i; b.y=j; b.cost=0; if(pho[i][j]==1) { looked++; q.push(b); } } bfs(); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { printf("%d ",f[i][j]); } printf("\n"); } return 0; }
好久没写广搜了，UPD（2019.6.18） 更新了部分注释，如果有问题可以评论区问，暑假应该会很快回复的
一遍过，没什么注意的，理论上每个点最多被刷新白点个数个次数，为了保险弄了个*2