OJ Board

The Online Judge board
https://onlinejudge.org/board/

297 - Quadtrees

https://onlinejudge.org/board/viewtopic.php?t=206851

Page 1 of 2

297 - BUG?

Posted: Wed Jun 26, 2002 8:53 pm
by broderic
Hello. I'm getting really frustrated with 297. Ok, here's my code.
It's pretty straightforward, but i'm getting an invalid memory reference.
however, i checked (by doing infinite loops), and i'm pretty sure
it's not referencing outside the p[33][33] array, or off the end of the
tree[1024] strings.

Here's the code:

Code: Select all


#include <stdio.h>

int p[2][33][33];
int index;

void color (int n, char *str, int size, int x, int y) {
  int i,j;

  if (str[index] == 'p') {
    index++;
    color(n, str, size/2, x+size/2, y);
    color(n, str, size/2, x, y);
    color(n, str, size/2, x, y+size/2);
    color(n, str, size/2, x+size/2, y+size/2);
  }
  else if (str[index] == 'f') {
    index++;
    for (i=y; i<y+size; i++) {
      for (j=x; j<x+size; j++) {
        p[n][i][j] = 1;
      }
    }
  }
  else index++;

}

int main () {
  int num,i,j,c,x,total;
  char tree[1024], tree2[1024];
  double a;

  scanf("%d\n", &num);
  for (i=0; i<num; i++) {
    scanf("%s\n%s\n", tree, tree2);

    memset(p,0,sizeof(p));

    index=0;
    color(0, tree, 32, 0, 0);
    index=0;
    color(1, tree2, 32, 0, 0);

    total=0;
    for (j=0; j<32; j++) {
      for (c=0; c<32; c++) {
        x = p[0][j][c] | p[1][j][c];
        if (x) total++;
      }
    }
    printf("There are %d black pixels.\n", total);
  }
  return 0;
}
Now, interestingly, if I just do a loop and read in strings, without
doing anything else, i get an invalid memory reference.

It seems to me like the input file is corrupted. anybody else have the
same problem, or am i just doing something extremely dumb? :)
Thanks for any input

Posted: Wed Jun 26, 2002 9:09 pm
by 10153EN
I don't think the input file is corrupted. On the other hand, I think it's your size of array tree and tree2 is too small. Consider a quad-tree with all the neighbour-pixels with different colour. i.e. sth like
bwbwbwbwbwbwbwbwbwb............bwbw
wbwbwbwbwbwbwbwbwbw............wbwb
.......
If the above quad-tree is one of the input, without the 'p' characters, there's altogether 1024 characters. Therefore the total length of the input line will be LONGER than 1024 characters.

I think changing to a larger array may help~

P.S. I have just taken a look at your input-reading part, since you mentioned there's problem there :wink:

297 - BUG?

Posted: Thu Jun 27, 2002 12:10 am
by broderic
doh!
you're so right, got it accepted first try.
well, it goes to show:if you get an error, almost EVERY time
it's your own fault.

thanks for helping me out.

Help, Prob 297-Quadtrees - *ALWAYS WA* - need critical input

Posted: Tue Mar 11, 2003 7:38 am
by Red Scorpion
If someone have time, please help me..... :x :cry: :cry:

This is my code:

Code: Select all

 cut...
HELP...HELP...HELP

Thanks,
RS

Posted: Fri Mar 21, 2003 10:11 am
by Red Scorpion
Ignore this I've got AC.
Thanks,
RS :lol: :lol: :lol: :lol:

297 !!

Posted: Wed Mar 10, 2004 1:52 pm
by Syeed
i'm getting WA for this code but i just can't find what's wrong! plz help!

Here's my code:


#include <stdio.h>
#include <math.h>

int inx, org_count, array[1025];
char a[20000];

void recur(int level)
{
int count_child = 0;
int i, j;
while(count_child < 4)
{
inx++;
if(a[inx] == 'p')
{
recur(level - 1);
}
else if(a[inx] == 'f')
{
j = (int)pow(4,level);
for( i = 1; i <= j; i++)
{
array[org_count + i] = 1;
}
org_count += j;
}
else if(a[inx] == 'e')
{
j = (int)pow(4,level);
org_count += j;
}
count_child++;
}
}

int main()
{
int n, count, i, j;
scanf("%d",&n);
for(i = 0; i < n ; i++)
{
for(j = 1; j <= 1024; j++)
array[j] = 0;
org_count = inx = 0;
scanf("%s",a);
recur(4);
org_count = inx = 0;
for(j = 1; j <= 1024; j++)
a[j] = 0;
scanf("%s",a);
recur(4);
count = 0;
for(j = 1; j <= 1024; j++)
{
if(array[j])
{
count++;
}
}
printf("There are %d black pixels.\n",count);
}
return 0;
}

[c][/c]

Posted: Thu Mar 11, 2004 12:21 am
by junbin
try this case:

1
f
f

ans should be 1024

Quadtrees (Problem 297): I get Output Limit Exceeded

Posted: Mon Oct 04, 2004 1:50 pm
by Yaron Wittenstein
I don't know why I get Output Limit Exceeded!
Here is my code, please help me!

Code: Select all



#include <stdio.h>

const int MAXN = 32;

int Image[MAXN][MAXN];
int CurPix;
int PixelNum;

void InitImage()
{
  int i, j;

  for(i = 0; i < MAXN; i++)
    for(j = 0; j < MAXN; j++)
      Image[i][j] = 0;
}


void Fill_Image(int x1, int x2, int y1, int y2)
{
  int i, j;

  for(i = x1; i <= x2; i++)
    for(j = y1; j <= y2; j++){
      if (Image[j - 1][i - 1] == 0) {
	Image[j - 1][i - 1] = 1;
	PixelNum++;
      }
    }
}

void Solve(char Str[], int x1, int x2, int y1, int y2)
{
  if (Str[CurPix] == 'p') {
      CurPix++;
      Solve(Str, (x1 + x2)/2 + 1, x2, y1, (y1 + y2)/2);
      CurPix++;
      Solve(Str, x1, (x1 + x2)/2, y1, (y1+y2)/2);
      CurPix++;
      Solve(Str, (x1 + x2)/2 + 1, x2, (y1 + y2)/2 + 1, y2);
      CurPix++;
      Solve(Str, x1, (x1 + x2)/2, (y1 + y2)/2 + 1, y2);
  }
  else if (Str[CurPix] == 'f')
    Fill_Image(x1, x2, y1, y2);
}


int main()
{
  int N;
  char Str1[1300], Str2[1300];
  int i;

  scanf("%d", &N);

  for(i = 0; i < N; i++) {
    scanf("%s", Str1);
    scanf("%s", Str2);

    PixelNum = 0;
    InitImage();
    CurPix = 0;
    Solve(Str1, 1, MAXN, 1, MAXN);

    CurPix = 0;
    Solve(Str2, 1, MAXN, 1, MAXN);

    printf("There are %d black pixels.\n", PixelNum);
  }

  return 1;
}
Please help me here!

Quadtrees (Problem 297): I get Output Limit Exceeded

Posted: Mon Oct 04, 2004 1:51 pm
by Yaron Wittenstein
I don't know why I get Output Limit Exceeded!
Here is my code, please help me!

Code: Select all



#include <stdio.h>

const int MAXN = 32;

int Image[MAXN][MAXN];
int CurPix;
int PixelNum;

void InitImage()
{
  int i, j;

  for(i = 0; i < MAXN; i++)
    for(j = 0; j < MAXN; j++)
      Image[i][j] = 0;
}


void Fill_Image(int x1, int x2, int y1, int y2)
{
  int i, j;

  for(i = x1; i <= x2; i++)
    for(j = y1; j <= y2; j++){
      if (Image[j - 1][i - 1] == 0) {
	Image[j - 1][i - 1] = 1;
	PixelNum++;
      }
    }
}

void Solve(char Str[], int x1, int x2, int y1, int y2)
{
  if (Str[CurPix] == 'p') {
      CurPix++;
      Solve(Str, (x1 + x2)/2 + 1, x2, y1, (y1 + y2)/2);
      CurPix++;
      Solve(Str, x1, (x1 + x2)/2, y1, (y1+y2)/2);
      CurPix++;
      Solve(Str, (x1 + x2)/2 + 1, x2, (y1 + y2)/2 + 1, y2);
      CurPix++;
      Solve(Str, x1, (x1 + x2)/2, (y1 + y2)/2 + 1, y2);
  }
  else if (Str[CurPix] == 'f')
    Fill_Image(x1, x2, y1, y2);
}


int main()
{
  int N;
  char Str1[1300], Str2[1300];
  int i;

  scanf("%d", &N);

  for(i = 0; i < N; i++) {
    scanf("%s", Str1);
    scanf("%s", Str2);

    PixelNum = 0;
    InitImage();
    CurPix = 0;
    Solve(Str1, 1, MAXN, 1, MAXN);

    CurPix = 0;
    Solve(Str2, 1, MAXN, 1, MAXN);

    printf("There are %d black pixels.\n", PixelNum);
  }

  return 1;
}
Please help me here!

Posted: Mon Oct 04, 2004 3:31 pm
by sohel
char Str1[1300], Str2[1300];

Your array size of Str1 and Str2 is too small.
Perhaps that's the cause of OLE.

It works now, I got AC thank!!!

Posted: Mon Oct 04, 2004 3:35 pm
by Yaron Wittenstein
Thank you very much!!

297 QuadTree WA HELP! GOING INSANE!

Posted: Tue Mar 29, 2005 12:19 am
by zenden
i keep on getting WA, i have tried many different test cases and they all work fine. but when i submit i get wrong answer :(
i have tried:
1
f
f
which works
has anyone got a text that i can try!

so frustrating :cry:

Posted: Tue Mar 29, 2005 12:22 am
by zenden
could it be possible that they might test an inclomplete tree?

297 Quadtrees(Runtime error)

Posted: Sun Jun 17, 2012 12:02 am
by 883030721
I have run the code on my pc with vs2008 corretly, but why got an RE?
My idea is to combine the two inputs, then caculate the black blocks with the depth.

Code: Select all

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 10000;
int level[50]={0,1024,256,64,16,4,1,0};

void Quadtrees(char *s1, char *s2)
{
 char s[MAXN]={'\0'};
 int count;
 for (int i=0,j=0,k=0 ; i < strlen(s1) && j < strlen(s2);)
 {
  if(s1[i] == 'p')
  {
   if(s2[j] == 'p')
   {
    i++;j++;s[k++]='p';
   }
   else if(s2[j] == 'f')
   {
    for(count = i+1; count < i+5; count++)
     if(s1[count] == 'p'){i = count;count = i;}
    i = count; j++; s[k++] = 'f';
   }
   else if(s2[j] == 'e')
   {
    s[k++] = 'p';
    for(count = i+1; count < i+5; count++)
    {
     s[k++] = s1[count];
     if(s1[count] == 'p'){i = count;count = i;}
    }
    i = count; j++;
   }
  }
  else if(s1[i] == 'e')
  {
   if(s2[j] == 'p')
   {
    s[k++] = 'p';
    for(count = j+1; count < j+5; count++)
    {
     s[k++] = s2[count];
     if(s2[count] == 'p'){j = count;count = j;}
    }
    j = count; i++;
   }
   else if(s2[j] == 'e')
   {
    i++;j++;s[k++]='e';
   }
   else if(s2[j] == 'f')
   {
    i++;j++;s[k++]='f';
   }

  }
  else if(s1[i] == 'f')
  {
   if(s2[j] == 'p')
   {
    for(count = j+1; count < j+5; count++)
     if(s2[count] == 'p'){j = count;count = j;}
    i++;j = count; s[k++] = 'f';
   }
   else if(s2[j] == 'e')
   {
    i++;j++;s[k++]='f';
   }
   else if(s2[j] == 'f')
   {
    i++;j++;s[k++]='f';
   }
  }
 }
 int sum = 0;
  for(int i = 0,depth=1,k=0; i < strlen(s); i++)
  {
  if(s[i] == 'f') sum += level[depth];
  else if(s[i] == 'p')
  {
   depth++;k++;
   int j;
   for(j = i+1;j < i+5; j++)
   {
    if(s[j] == 'f') sum += level[depth];
    else if(s[j] == 'p'){i=j;j=i;k++;depth++;}
    else continue;
   }
   i = j-1;
   depth -= k;
   depth++;
  }
  else continue;
  }
 printf("There are %d black pixels.\n",sum);
}

int main()
{
 int N;
 char s1[MAXN],s2[MAXN];
 scanf("%d",&N);
 while(N--)
 {
  scanf("%s%s",&s1,&s2);
  Quadtrees(s1,s2);
 }
 return 0;
}

Re: 297 Quadtrees(Runtime error)

Posted: Tue Jun 19, 2012 4:04 am
by brianfry713
Input:

Code: Select all

1
pppppfefepffefpeeffpfffeppffefpffeepfeefpfeffppeeefpfefepefffpfeeeppefefpfeefpffeepfefepppeeffpeefepfffepfffeppeefepefffpeefepffefpfpffefpefefpffeeppffefpfeeepefefeppfpfeefpfefeeppeffepfefepfeeepfefeppfefepefefpeeeffppeffepffeepfffepeefepppfeefpefeepefefpfeeeppeeefpfeffpefeffppffefpfefepeeffpfeeeppfffepefeepfefepffefppppfffefpffeffpfpfeefpeeefpfffepfpffefpefffpfefeppefeepeefepefffpffefpppfeefpffeeepefefppfeffffpefffppeefepefffpefffpeeefppeeffepefefpeffepppfeefpfffepfeeepefffpfpeeffpffeepffeeppffeepfeffpfeffpefefppefeffpffeepefffpppefeefpfefepeefeppffeepeffepeeffpeeffppefeepeeefpeefepeeffppefeepefffpfefepefeepppepfefepfeefpfeffppeeefpeefepeeefpffefppeeefpfffepffeepeefeppeeffpfefepffefpeeffpppeffepfeeefpeeffppffefpfeffpffefpffefppfeffpeeffpeefepeefeppfefepeeefpeefepfeefpppeeefpeeefpeeffpffeeppfffepfeeepffeepefefppfefepeeefepeefeppeeffpeffepfeefpefefpppeffepfeffpfeeepffefppfeefpfefepeeefpeefeppeefepfefepffeepeeefppefeepffefepffefppppeeefpfeffpfeeepfeefppefffpfeffpfeefpfefeppeeffpeeffpfeffpeeefppffefpfeefpfeffpeffepppffeepefeepefefpeeefppeeffpefffpeffepfffeppfeefpfefepfeeepeeefppeeffpfffepffeepeefepppfeeepefefpeeefpfeffppffeepefffpeefepfeeeppfffepeeffffppeeffpeeffpffefpfeeepppeefepeefepffefpfeffpfpffeeffpepefefpfeefpffefpfpffeepffeepfffe
pppppfefepfeffpeefepeeefppfeefpfefepffeepffefppfeffpefefpeeefpfefeppfeffpeeffpfffefpppeffffpfeefpeeefppefefpfefepeffepefffppffeepefeepfeffpfeefppeefepfeefpefffpeefepppfeffpfeefffppfefepffeepffeepeeffppfefefpfeeeeppeeffpeeffpeeefpeeffpppfeefpfeffpfeeeeppefffpffefpffefpeeefpefpeffepfeefppffefpefffpeeffpfffeppppffeeepffefpfeeeppeeefpfffeepeeffppffefpfeffpefefpfeefppffeepefeepeffepeeefpppfeffpfffepfeefpffefppefefpefefpfeefpeefeppfeefpefffpeeefpfffeppfeffpeefepefeepfeeepppffefpeefeepfeefppefeefpffeepefefppefffpffefpeffepfefepepfefepeefepefffpppeeefpfeefpfffepeefeppfeeepfeefpefefpfffeppfeffpfeeepeefepeeefppfeefpfffepfefepefeeppppffefpefefpfffepfffeppfeefpefefpefeepefeeppefefepfeffpefffppefefpeeffpfefefppffpefffeppfeeepeffepfefefppeeffpfeeepefefpfeffppffeepfeeepfeeepfeeepppefeepffeffpefeeppffefpfeefpffeepeeffppeeffpefeepfefepeffeppeffepfeefpeefepfeffpppeffepefffpfffepffeeppfffepefeepeffepfeeeppefefpfeeepeefepeefeppfefepeeffpfffepfeffppppefeepeeffpffefpfefeppefefpefffpefeffppffeepefffpffeepeffeppfeffpefffpfefepefefpppffefpfeeepeeffpffeeppefffpefffpfeffpefefppefffpfefepfeeffppfefepfefepeefepeeefpppfefffpeeefpefffppfffeepeefepefffpepeeefpeeefpfeffppeeffpefffpefffpfefepppfeefpeffepefeepefeeppeffepfeeepefeepefeeppfeffpffeepfefeeppffeepeeefpffeee
The AC output is 788. Your code gives a seg fault when depth goes negative.
All times are UTC+02:00
Page 1 of 2

Powered by phpBB® Forum Software © phpBB Limited