SDOI 2005 毒瘤 位图
#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));
//int i;
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;
if(f[x][y]<cost) continue;
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;
}
一遍过，没什么注意的，理论上每个点最多被刷新白点个数个次数，为了保险弄了个*2
更多精彩
