Tuesday, February 07, 2012

FloodFill With BFS in 4 direction(657 - The die is cast)

#include<stdio.h>
#include<algorithm>
#define sz 11000

using namespace std;

struct st
{
int x, y;
}Q[sz*sz] ;

char mat[60][60];
int store[sz],res;

void BFS( st s )
{
st u ;
int front=0,rear=0;
int i, rr[4]={0,0,1,-1}, cc[4] = {1,-1,0,0};
mat[s.x][s.y] = '*' ;
Q[rear++] = s ;

while( front!=rear )
{
u = Q[front++] ;
for(i=0;i<4;i++)
{
if( mat[u.x+rr[i]][u.y+cc[i]] == 'X')   //??
{
mat[u.x+rr[i]][u.y+cc[i]]= '*';
Q[rear].x = u.x+rr[i] ;
Q[rear].y = u.y+cc[i] ;
rear++;
}
}
}
}
void BFS1( st s )
{
    printf("i = = %d j == %d\n",s.x,s.y);
st u ,v;
int front=0,rear=0;
int i, rr[4]={0,0,1,-1}, cc[4] = {1,-1,0,0};
mat[s.x][s.y] = '.';
    Q[rear++] = s ;

    while( front!=rear )
    {
        printf("front = %d %d\n",front,rear);
        u = Q[front++] ;

        for(i=0;i<4;i++)
        {
            if(mat[u.x+rr[i]][u.y+cc[i]] == 'X')
            {
                store[res]++;
                v.x=u.x+rr[i];
                v.y=u.y+cc[i];
                printf("v = %d %d\n",v.x,v.y);
                BFS(v);
            }
            else
            {
                printf("u = %d %d\n",u.x,u.y);
                mat[u.x+rr[i]][u.y+cc[i]]= '.';
                Q[rear].x = u.x+rr[i] ;
                Q[rear].y = u.y+cc[i] ;
                rear++;
            }
        }
    }
}

int main()
{
freopen("657.txt","r",stdin);
int r, c, i, j,kase=1;
char aa;
st u ;

while(scanf("%d %d ",&c,&r) == 2 && (r||c))
{
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
scanf("%c",&aa);
mat[i][j] = aa;
}
scanf("%c",&aa);
}
res = 0 ;

for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
if( mat[i][j] != '.')
{
u.x = i ; u.y = j ;
printf("i == %d %d \n",i,j);
BFS1(u);
res++;
}
}
}

sort(store,store+res);

printf("Throw %d\n",kase++);
for(i=0;i<res;i++)
if(store[i]!=0)
{
printf("%d",store[i++]);
break;
}
for(;i<res;i++)
printf(" %d",store[i]);

printf("\n\n");
for(i=0;i<10100;i++)
            store[i] = 0;
}
return 0;
}

No comments:

Post a Comment