Follows 352.c (Total 90 lines):
/* @JUDGE_ID:4461XX 352 C "BFS" */
/* A */
#include<stdio.h>
#define MAX 25
char map[MAX][MAX+1] ;
int d ;
int Run( void )
{
int num=0 , i , j , x , y ;
int q[MAX*MAX][2] , head , tail ;
for( i=0 ; i<d ; ++i )
for( j=0 ; j<d ; ++j )
if( map[i][j]=='1' ){
++num ;
q[0][0] = i ;
q[0][1] = j ;
map[i][j] = 0 ;
for( head=tail=0 ; head<=tail ; ++head ){ /*BFS*/
x = q[head][0] ;
y = q[head][1] ;
if( x-1>=0&&y-1>=0&&map[x-1][y-1]=='1' ){
++tail ;
q[tail][0] = x-1 ;
q[tail][1] = y-1 ;
map[x-1][y-1] = 0 ;
}
if( x-1>=0&&map[x-1][y]=='1' ){
++tail ;
q[tail][0] = x-1 ;
q[tail][1] = y ;
map[x-1][y] = 0 ;
}
if( x-1>=0&&y+1<d&&map[x-1][y+1]=='1' ){
++tail ;
q[tail][0] = x-1 ;
q[tail][1] = y+1 ;
map[x-1][y+1] = 0 ;
}
if( y-1>=0&&map[x][y-1]=='1' ){
++tail ;
q[tail][0] = x ;
q[tail][1] = y-1 ;
map[x][y-1] = 0 ;
}
if( y+1<d&&map[x][y+1]=='1' ){
++tail ;
q[tail][0] = x ;
q[tail][1] = y+1 ;
map[x][y+1] = 0 ;
}
if( x+1<d&&y-1>=0&&map[x+1][y-1]=='1' ){
++tail ;
q[tail][0] = x+1 ;
q[tail][1] = y-1 ;
map[x+1][y-1] = 0 ;
}
if( x+1<d&&map[x+1][y]=='1' ){
++tail ;
q[tail][0] = x+1 ;
q[tail][1] = y ;
map[x+1][y] = 0 ;
}
if( x+1<d&&y+1<d&&map[x+1][y+1]=='1' ){
++tail ;
q[tail][0] = x+1 ;
q[tail][1] = y+1 ;
map[x+1][y+1] = 0 ;
}
}
}
return num ;
}
int main( void )
{
int i , times ;
for( times=1 ; scanf( "%d\n" , &d )==1 ; ++times ){
for( i=0 ; i<d ; ++i ) gets( map[i] ) ;
printf( "Image number %d contains %d war eagles.\n" , times , Run() ) ;
}
return 0 ;
}
Back to statistics
Ya-Lin Huang (C)
huangyl@gmail.com