Page 2 of 4
Posted: Mon Jul 22, 2002 5:48 pm
by 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!
argh!
Posted: Thu Aug 29, 2002 3:59 am
by 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]
Posted: Sat Aug 09, 2003 7:08 pm
by 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?
Posted: Mon Oct 13, 2003 7:08 pm
by 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.
776 - Runtime Error (SIGSEGV) Please Help
Posted: Wed Oct 13, 2004 4:52 pm
by 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]
Posted: Thu Oct 14, 2004 8:32 am
by 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
Posted: Wed Nov 01, 2006 9:18 pm
by 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;
}
776: PE
Posted: Sat Jan 06, 2007 3:37 pm
by 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?
Posted: Sat Jan 06, 2007 6:55 pm
by 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
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.
Posted: Sun Jan 07, 2007 10:23 am
by helloneo
Good example..
Finally got AC..
Thanks..
Posted: Wed Apr 11, 2007 6:48 pm
by 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;
}
Posted: Wed Apr 11, 2007 11:01 pm
by 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.
Posted: Wed Apr 18, 2007 6:35 pm
by albet_januar
em.. how i can speed up my code ??
any idea??
thx
Posted: Wed Apr 18, 2007 7:54 pm
by 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.
Posted: Sun Jul 29, 2007 8:28 pm
by 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;
}