x直接翻译那个式子的意思是,对于(i,j),找离他曼哈顿距离最近的且为1的(x,y),并记b[i][j]为他们的曼哈顿距离.
不妨将这个式子反过来看.就是用为1的(x,y)去更新其它点的b[i][j];
但一个一个点来做复杂度过高.将所有为1的点都加入队列再进行bfs即可.
//Wan Hong 3.0
//notebook
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
typedef long long ll;
typedef std::pair<ll,ll> pll;
ll read()
{
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
else c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
bool umin(ll &a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
bool umax(ll &a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
/**********/
#define MAXN 1011
#define x first
#define y second
ll a[MAXN][MAXN],b[MAXN][MAXN],n,m;
const ll mx[5]={0,-1,0,1,0},my[5]={0,0,1,0,-1};
std::queue<pll>q;
bool in(ll x,ll y)
{
return x>0&&x<=n&&y>0&&y<=m;
}
void bfs()
{
while(!q.empty())
{
ll sx=q.front().x,sy=q.front().y;q.pop();
for(ll i=1;i<=4;++i)
{
ll vx=sx+mx[i],vy=sy+my[i];
if(in(vx,vy)&&b[vx][vy]==-1)
{
b[vx][vy]=b[sx][sy]+1;
q.push(pll(vx,vy));
}
}
}
}
int main()
{
memset(b,-1,sizeof b);
n=read(),m=read();
for(ll i=1;i<=n;++i)
for(ll j=1;j<=m;++j)
{
char c=getchar();
while(c!='0'&&c!='1')c=getchar();
a[i][j]=c-'0';
if(a[i][j]==1)
{
b[i][j]=0;
q.push(pll(i,j));
}
}
bfs();
for(ll i=1;i<=n;++i)
for(ll j=1;j<=m;++j)
printf("%lld%c",b[i][j],j==m?'\n':' ');
return 0;
}
一个一个来做是不是还要重新更新d数组呀