记录编号	12448	评测结果	AAAAAAAAAAAAAAAA
题目名称	[POI 1999] 位图	最终得分	100
用户昵称	yanzheng	是否通过	通过
代码语言	C	运行时间	0.262 s
提交时间	2009-09-12 11:50:43	内存使用	1.38 MiB

#include <stdio.h>

int n,m,g[183][183]={0},f[183][183];
int list[100000][2],inl[183][183]={0};
int t=0,q=0;

void bfs()
{
    int x,y,i,j,k;
    if(t>q) return;
    x=list[t][0];
    y=list[t][1];
    inl[x][y]=0;
    t++;
    if(f[x+1][y]>f[x][y]+1 && x<=n)
    {
        f[x+1][y]=f[x][y]+1;
        if(!inl[x+1][y])
        {
            list[q][0]=x+1;
            list[q][1]=y;
            q++;
        }
    }

    if(f[x][y+1]>f[x][y]+1 && y+1<=m)
    {
        f[x][y+1]=f[x][y]+1;
        if(!inl[x][y+1])
        {
            list[q][0]=x;
            list[q][1]=y+1;
            q++;
        }
    }

    if(f[x-1][y]>f[x][y]+1 && x>1)
    {
        f[x-1][y]=f[x][y]+1;
        if(!inl[x-1][y])
        {
            list[q][0]=x-1;
            list[q][1]=y;
            q++;
        }
    }

    if(f[x][y-1]>f[x][y]+1 && y>1)
    {
        f[x][y-1]=f[x][y]+1;
        if(!inl[x][y-1])
        {
            list[q][0]=x;
            list[q][1]=y-1;
            q++;
        }
    }
    bfs();
}

int main()
{
    FILE *in,*out;
    in=fopen("bit.in","r");
    out=fopen("bit.out","w");
    int i,j,k;
    char tmp[184];

    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=n;i++)   
    {
        fscanf(in,"%s",&tmp);
        for(j=1;j<=m;j++)
        {
            g[i][j]=(int)(tmp[j-1]-'0');
            if(g[i][j])
            {
                f[i][j]=0;
                list[q][0]=i;
                list[q][1]=j;
                inl[i][j]=1;
                q++;
            }
            else
                f[i][j]=100000;
        }
    }

    bfs();

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)   
        {
            fprintf(out,"%d",f[i][j]);
        }
        fprintf(out,"\n");
    }
    return 0;
}