多源bfs
上英语课的时候再摘抄本上捣鼓捣鼓捣鼓出来了,哈哈哈哈,代码神童!
重点就是要再=把所有为1的点第一时间直接入队,然后再写个bfs模板就行,实际上的确是可以实现的,我已经模拟过了
注意搜过得不能再搜啊
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
queue<PII> q;
int a[N][N],b[N][N];
int m,n;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
a[i][j]=c-'0';
if(a[i][j])
{
q.push({i,j});
b[i][j]=0;
}
}
}
while(!q.empty())
{
PII u=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int x=u.first+dx[i];
int y=u.second+dy[i];
if(x>0&&x<=n&&y>0&&y<=m&&b[x][y]==0&&a[x][y]==0)
{
b[x][y]=b[u.first][u.second]+1;
q.push({x,y});
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<b[i][j]<<' ';
}
puts("");
}
return 0;
}