776 - Monkeys in a Regular Forest

[htl]

I modified it 3 times and eventually got AC. Although it spent much memory (I declare monkey[][] and table[][] as 1000*1000),I was ranked 21!

[broderic]

argh! I'm pulling my hair out in frustration with this problem!
Can anybody give me a test case where this fails?

Thanks in advance,
Broderick

[c]
#include <stdio.h>
#include <assert.h>

int w,h;
char grid[2048][2048],out[2048][2048];
int dx[] = { 0, 1,1,1,0,-1,-1,-1};
int dy[] = {-1,-1,0,1,1, 1, 0,-1};

void flood(int y, int x, int c, char a) {
int i;
grid[y][x]=0;
out[y][x]=c;
for (i=0; i<8; i++)
if (grid[y+dy][x+dx]==a) flood(y+dy,x+dx,c,a);
}

int main () {
int i,j,cw,c,another=1,col[2048];
char str[14096],t[5];

while (another) {
memset(grid,0,sizeof(grid));
memset(out,0,sizeof(out));
memset(col,0,sizeof(col));
another = 0;
for (i=1,w=0; ; i++) {
if (!gets(str)) break;
if (str[0]=='%') {
another = 1;
break;
}
for (j=0,cw=0; j<strlen(str); j++)
if (str[j]!=' ') grid[1+cw++]=str[j];
if (cw>w) w=cw;
}

h = i-1;
for (i=1,c=1; i<=h; i++) {
for (j=1; j<=w; j++) {
if (grid[j])
flood(i,j,c++,grid[j]);
}
}
for (i=1; i<=w; i++) {
for (j=1; j<=h; j++)
if (out[j]>col) col = out[j][i];
}
for (i=1; i<=h; i++) {
for (j=1; j<=w; j++) {
if (j==1) {
if (col[j]<10) printf("%d", out[i][j]);
else if (col[j]<100) printf("%2d", out[i][j]);
else if (col[j]<1000) printf("%3d", out[i][j]);
else if (col[j]<10000) printf("%4d", out[i][j]);
else if (col[j]<100000) printf("%5d", out[i][j]);
}
else {
if (col[j]<10) printf("%2d", out[i][j]);
else if (col[j]<100) printf("%3d", out[i][j]);
else if (col[j]<1000) printf("%4d", out[i][j]);
else if (col[j]<10000) printf("%5d", out[i][j]);
else if (col[j]<100000) printf("%6d", out[i][j]);
}
}
printf("\n");
}
printf("%%\n");
}
return 0;
}[/c]

[bobi1978]

I have 3 questions about this problem:

1) xenon said that we shoul think about BIG FORESTS! How big it can be?
I use char forest[2500][2500]. Is this enough? Beyond this I receive MEMORY LIMIT.

2) What about THE LAST FOREST? How INPUT ends? is it EOF, and should I print "%" after the LAST FOREST?

3) Are there rows with various number of letters, and what to do in such case?
ex:
------------------
A A A B B B
C
D D D
F F F F F F
G
%
------------------
what is the OUTPUT for this INPUT?

[hackfox]

Bobi,
1. You can try to allocate the array dynamically. I use the C function
malloc and realloc and free to do all thing.

2.The last forest ends with EOF, not %. But for output, you shold print
a % after the last input.

3.I onlly deal with rectangle matrix. So I guess the number of letter
in every row is of the same number.

[A1]

Can any body pls help me to find where is my porblem in this code
It is getting Runtime Error (SIGSEGV) again and again

[cpp]
#include <stdio.h>
#include <string.h>

char grid [1005][1005];
int csize[1005],col,row;
void dfs(int ,int ,int, char);

void reset()
{
int i;
for(i=0;i<1005;i++)
{
csize=0;
}
}
int main()
{
int N=1,i,j,count;
char c;

while(N)
{

reset();
i=j=0;
while(c=getchar())
{
if(c=='%')
{
getchar();
break;
}
if(c==EOF)
{
N=0;
grid[j]='\0';
break;
}
if(c!=' ' && c!='\n')
grid[j++]=c;

if(c=='\n')
{
grid[j]='\0';
i++;
j=0;
}

}//End of input taking

row=i;
count=1;
col=strlen(grid[0]);

for(i=0;i<row;i++)
for(j=0;j<col;j++)
{
if(grid[j]>='A'&&grid[j]<='Z'||grid[j]>='a'&&grid[j]<='z')
dfs(i,j,count++,grid[j]);
}

for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
if(csize[j]<10)
printf("%d",grid[j]);
else if(csize[j]<100)
printf("%2d",grid[i][j]);
else
printf("%3d",grid[i][j]);
if(j<col-1)
printf(" ");
}
printf("\n");
}

printf("%%\n");
}
return 0;
}

void dfs(int f,int s, int num,char c)
{
grid[f][s]=num;
int i,j;
if(num>csize[s])
csize[s]=num;
for(i=f-1;i<f+2;i++)
for(j=s-1;j<s+2;j++)
{
if(i>=0&&i<=row&&j>=0&&j<=col)
if(grid[i][j]==c)
dfs(i,j,num,c);
}
}
[/cpp]

[A1]

At last I got AC with PE!

I completely change my previous code.
I think problem was for stack overflow and judge reply RTE

Thanks

[kolpobilashi]

i am getting WA for this code...anybody knows why??

Code: Select all

#include<stdio.h>
#include<string.h>
#define M 1000
char input[M][M];
char Grid[M][M];
char Visit[M][M];
int output[M][M],col[M]={0};
int Move[8][2]={1,1,1,0,0,1,-1,-1,-1,0,0,-1,-1,1,1,-1},b=1;
char ping;
void dfs(int r, int c) 
{
	int i;
	for (i = 0; i < 8; i++) 
	{
		int newr = Move[i][0] + r;
		int newc = Move[i][1] + c;
		if (Visit[newr][newc]&&Grid[newr][newc]==ping) 
		{
			Visit[newr][newc] = false;
			Grid[newr][newc]=b+'0'; 
			output[newr][newc]=b; 
			dfs(newr, newc);
		}
	}
}
int main()
{
	int i=0,j,k,p,line=0;
	while(gets(input[i]))
	{
		
			
			memset(Visit,true,sizeof(Visit));
			memset(col,0,sizeof(col));
			b=1;
			p=0;
			for(j=0;j<strlen(input[i]);j++)
					if(input[i][j]!=' ')Grid[i][p++]=input[i][j];
					Grid[i][p]='\0';
			i++;
			int l,p,flag=0;
		
			while(1)
			{
					gets(input[i]);
					if(input[i][0]=='%'||input[i][0]==NULL)break;
					 p=0;
					for(j=0;j<strlen(input[i]);j++)
					if(input[i][j]!=' ')Grid[i][p++]=input[i][j];
					Grid[i][p]='\0';
					i++;
					
			}
					
			for(k=0;k<i;k++)
				for(j=0;j<(strlen(Grid[k]));j++)
				{
					if(Visit[k][j])
					{
						
						ping=Grid[k][j];
						Grid[k][j]=b+'0';
						output[k][j]=b;
						dfs(k,j);
						b++;
					
					}
				}
			int len;
			len=strlen(Grid[0]);
			for(j=0;j<len;j++)
			for(k=0;k<i;k++)
			if (output[k][j]>col[j]) col[j] = output[k][j]; 
			for(k=0;k<i;k++)
			{
				for(j=0;j<len;j++)
				{
					if (j==0)
					{ 
					if (col[j]<10) printf("%d",output[k][j]); 
					else if (col[j]<100) printf("%2d",output[k][j]); 
					else if (col[j]<1000) printf("%3d",output[k][j]); 
					else if (col[j]<10000) printf("%4d",output[k][j]); 
					else if (col[j]<100000) printf("%5d",output[k][j]); 
					} 
					else
					{ 
					if (col[j]<10) printf("%2d",output[k][j]); 
					else if (col[j]<100) printf("%3d",output[k][j]); 
					else if (col[j]<1000) printf("%4d",output[k][j]); 
					else if (col[j]<10000) printf("%5d",output[k][j]); 
					else if (col[j]<100000) printf("%6d",output[k][j]); 
					} 
					//printf("%d ",output[k][j]);
				}
				printf("\n");
			}
			
			printf("%%\n");
			memset(Grid,0x0,sizeof(Grid));
			memset(input,0x0,sizeof(input));
			memset(output,0x0,sizeof(output)); 
			i=0;
	}
					
	return 0;
}

[Donotalo]

for the following input:

Code: Select all

A B D E C C D
F F W D D D D
P W E W W W W
%
a A b B c d E t
a a a a a c c t
e f g h c a a t

i got PE for both of the output:

Code: Select all

1 2 3 4 5 5 3
6 6 7 3 3 3 3
8 7 9 7 7 7 7
%
1  2  3  4 5 6 7 8
1  1  1  1 1 5 5 8
9 10 11 12 5 1 1 8
%

and

Code: Select all

1 2 3 4 5 5 3
6 6 7 3 3 3 3
8 7 9 7 7 7 7
%
1  2  3  4 5 6 7 8
1  1  1  1 1 5 5 8
9 10 11 12 5 1 1 8
%

can anyone help me to get this problem accepted?

[Jan]

Try the I/O sets.

Input:

Code: Select all

A A D E C C D
F F A D a b D
P A E A A D P
%
a b c d e f g h
i j k l m n o p
q r s t u v w x

Output:

Code: Select all

1 1  2 3 4 4  5
6 6  1 2 7 8  5
9 1 10 1 1 5 11
%
 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24(<- No trailing space in any line)
%

Hope these help.

[helloneo]

Good example..
Finally got AC..
Thanks..

[albet_januar]

i got WA.. but i do the sample i/o
pliz help me..

can anybody give sample input??

thx;;

Code: Select all

#include <cstdio>
#include <cstring>
#define MAX 500

char input[ MAX + 1 ][ MAX + 1 ];
char out[ MAX + 1 ][ MAX + 1 ];
int check[ MAX + 1 ];
int ind;

void floodfill( char huruf, int i, int j , int c)
{
 if( i >= 0 && j >= 0 )     
 {
     int len = strlen( input[ i ] );
     if( i < ind && j < len )
     {
         if( input[ i ][ j ] == huruf )
         {
          input[ i ][ j ] = ' ';
          out[ i ][ j ] = c;
          
          char temp[ 100 ];
          sprintf( temp, "%d", c );
          len = strlen( temp );
          if( check[ j ] < len ) check[ j ] = len;
          
          floodfill( huruf, i - 1, j, c );
          floodfill( huruf, i - 1, j - 1, c );
          floodfill( huruf, i - 1, j + 1, c );
          floodfill( huruf, i , j - 1, c );
          floodfill( huruf, i , j + 1, c );
          floodfill( huruf, i + 1, j , c );
          floodfill( huruf, i + 1, j - 1, c );
          floodfill( huruf, i + 1, j + 1, c );
                       
         }
     }    
 }
}

void process( )
{
 int i, j, len;
 int counter = 1;
 for(i = 0 ; i < ind ; i++ )
 {
  len = strlen( input[ i ] );
  for(j = 0 ; j < len ; j++ )
  {
   if( input[ i ][ j ] != ' ' ) floodfill( input[ i ][ j ], i, j , counter++);        
  }        
 }  
 
 int max, k;
 char tmp[ 100 ];
  
 for( i = 0 ; i < ind ; i++ )
 {
      len = strlen( input[ i ] );
      for( j = 0 ; j < len ; j++ )
      {
         sprintf( tmp, "%d", out[ i ][ j ] );
         k = strlen( tmp );
                  
         if( k - check[ j ] != 0 )
         {
            int l = check[ j ] - k;
            while( l-- ) printf(" ");
         }
         
         printf("%d", out[ i ][ j ] );    
         
         if( j < len - 1 ) printf(" ");
              
      }  
      
      printf("\n");   
 }
 
 printf("%%\n"); 
  
}

void init( )
{
 for(int i = 0 ; i < MAX ; i++ )
 {
  memset( input, '\0', sizeof( input ) );
  check[ i ] = 0;
 }     
}

int main()
{
 char temp[ MAX + 1 ];
 ind = 0;
  
 
 init();
 while( gets( temp ) )
 {
  if( temp[ 0 ] == '%' )
  {
  
   process( );
   ind = 0;
   init();
  }
  else
  {
   int c = 0;
   int len = strlen( temp );
   for(int i = 0; i < len;i++)
   {
    if( temp[ i ] != ' ' ) input[ ind ][ c++ ] = temp[ i ];         
   }    
     
   ind++;
   
  }
    
 }
 
 process( );
 
 return 0;    
}

[Jan]

I think your code is correct, but it's too slow. Increase the value of MAX to 1000. I have used '1000' in my accepted code.

Hope it helps.

[albet_januar]

em.. how i can speed up my code ??

any idea??
thx

[Jan]

Finally got your error. Change the following things...

Code: Select all

int out[ MAX + 1 ][ MAX + 1 ]; // not char out[][] 

And look at your init() function. You are initializing input[][], MAX times . Just initialize it once.

Hope these help.

[chetan]

why RE ???

Code: Select all

# include <iostream>
# include <algorithm>
# include <cstring>
# include <cstdlib>
# include <cstdio>

using namespace std;

char arr[1010][1010];
int r,c,seen[1010][1010];
 
void ff(int i,int j,int n,char x)
{
    arr[i][j]=n;
    seen[i][j]=1;
                         //up
                    if(i-1>=0 && arr[i-1][j]==x && ! seen[i-1][j])
                        ff(i-1,j,n,x);        
                    //down
                    if(i+1<r && arr[i+1][j]==x&& !seen[i+1][j])
                        ff(i+1,j,n,x);
                    //left
                    if(j-1>=0 && arr[i][j-1]==x && !seen[i][j+1])
                        ff(i,j-1,n,x);
                    //right
                    if(j+1<c && arr[i][j+1]==x && !seen[i][j+1])
                        ff(i,j+1,n,x);
                    //up left
                    if(i-1>=0 && j-1>=0 && arr[i-1][j-1]==x && !seen[i-1][j-1])
                        ff(i-1,j-1,n,x);
                    //up right
                    if(i-1>=0 && j+1<c && arr[i-1][j+1]==x && !seen[i-1][j+1])
                        ff(i-1,j+1,n,x);
                    //down left
                    if(i+1<r && j-1>=0 &&arr[i+1][j-1]==x && !seen[i+1][j-1])
                        ff(i+1,j-1,n,x);
                    //down right
                    if(i+1<r && j+1<c && arr[i+1][j+1]==x && !seen[i+1][j+1])
                        ff(i+1,j+1,n,x);
}

 
int main()
{
   
    int i,j;
    char ch;
    
    while(1)
    {
        i=j=0;
        memset(seen,0x0,sizeof(seen));
        memset(arr,0x0,sizeof(arr));
        
        while((ch = getchar()) !='%')
        {
            if(ch == EOF)   return 0;
            else if(ch ==' ')   continue;
            else if(ch == '\n')
            {
                i++;    
                j=0;
                continue;
            }
            else arr[i][j++]=ch;
            c=j;
        
        }
        
        r=i;
        getchar();
      
        //cout<<r<<' '<<c<<'\n';
       
        int n=1;
        for(i=0;i<r;i++)
            for(j=0;j<c;j++)
            {
                if(!seen[i][j])
                {
                    ff(i,j,n,arr[i][j]);
                    n++;
                }
            }
            
        char a[10];
        int b[500]={0};
        sprintf(a,"%d",n);
        int l=strlen(a);
            for(i=0;i<c;i++){
                /*maks=0;*/
                for(j=0;j<r;j++)
                {
                    sprintf(a,"%d",arr[j][i]);
                    int l=strlen(a);
                    if(l>b[i])  b[i]=l;
                }
             
            }
        
        for(i=0;i<r;i++)
        {
            for(j=0;j<c;j++){
                if(j!=0)
                printf("%*d",b[j]+1/*l*/,arr[i][j]);
                else 
                printf("%*d",b[j],arr[i][j]);
            }
                
            printf("\n");
        }
        printf("%%\n");
    }
   return 0;
}