#include <stdio.h>
#include <string.h>

struct data
{
    int x,y;
}queue[20000],now,next;

int in,out;
int mov[8][2]={{-1,0}, {-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1}};
char field[102][102];
int m,n;
int ans;
int k;

void bfs(int i,int j)
{
    in=out=0;
    queue[in].x=i;
    queue[in].y=j;
    field[i][j]='*';
    in++;

    while(in!=out)
    {
        now=queue[out++];
        for(k=0;k<8;k++)
        {
            next.x=now.x+mov[k][0];
            next.y=now.y+mov[k][1];
            if(field[next.x][next.y]=='@')
            {
                field[next.x][next.y]='*';
                queue[in++]=next;
            }
        }
    }
}

int main()
{
    //freopen("in","r",stdin);
    int i,j;

    while(scanf("%d%d",&m,&n),m)
    {
        ans=0;
        memset(field,'*',sizeof(field));

        while(getchar()==' ');
        for(i=1;i<=m;i++)
        {
            scanf("%s",field[i]+1);
        }
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(field[i][j]=='@')
                {
                    bfs(i,j);
                    ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
}

• Re:BFS，400K,0MS水过！！！（附代码） (1404) zhongshijun 2013-01-20 20:22:36