297 - Quadtrees

[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

[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

[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.

[Red Scorpion]

If someone have time, please help me.....

This is my code:

Code: Select all

 cut...

HELP...HELP...HELP

Thanks,
RS

[Red Scorpion]

Ignore this I've got AC.
Thanks,
RS

[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]

[junbin]

try this case:

1
f
f

ans should be 1024

[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!

[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!

[sohel]

char Str1[1300], Str2[1300];

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

[Yaron Wittenstein]

Thank you very much!!

[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

[zenden]

could it be possible that they might test an inclomplete tree?

[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;
}

[brianfry713]

Input:

Code: Select all

1
pppppfefepffefpeeffpfffeppffefpffeepfeefpfeffppeeefpfefepefffpfeeeppefefpfeefpffeepfefepppeeffpeefepfffepfffeppeefepefffpeefepffefpfpffefpefefpffeeppffefpfeeepefefeppfpfeefpfefeeppeffepfefepfeeepfefeppfefepefefpeeeffppeffepffeepfffepeefepppfeefpefeepefefpfeeeppeeefpfeffpefeffppffefpfefepeeffpfeeeppfffepefeepfefepffefppppfffefpffeffpfpfeefpeeefpfffepfpffefpefffpfefeppefeepeefepefffpffefpppfeefpffeeepefefppfeffffpefffppeefepefffpefffpeeefppeeffepefefpeffepppfeefpfffepfeeepefffpfpeeffpffeepffeeppffeepfeffpfeffpefefppefeffpffeepefffpppefeefpfefepeefeppffeepeffepeeffpeeffppefeepeeefpeefepeeffppefeepefffpfefepefeepppepfefepfeefpfeffppeeefpeefepeeefpffefppeeefpfffepffeepeefeppeeffpfefepffefpeeffpppeffepfeeefpeeffppffefpfeffpffefpffefppfeffpeeffpeefepeefeppfefepeeefpeefepfeefpppeeefpeeefpeeffpffeeppfffepfeeepffeepefefppfefepeeefepeefeppeeffpeffepfeefpefefpppeffepfeffpfeeepffefppfeefpfefepeeefpeefeppeefepfefepffeepeeefppefeepffefepffefppppeeefpfeffpfeeepfeefppefffpfeffpfeefpfefeppeeffpeeffpfeffpeeefppffefpfeefpfeffpeffepppffeepefeepefefpeeefppeeffpefffpeffepfffeppfeefpfefepfeeepeeefppeeffpfffepffeepeefepppfeeepefefpeeefpfeffppffeepefffpeefepfeeeppfffepeeffffppeeffpeeffpffefpfeeepppeefepeefepffefpfeffpfpffeeffpepefefpfeefpffefpfpffeepffeepfffe
pppppfefepfeffpeefepeeefppfeefpfefepffeepffefppfeffpefefpeeefpfefeppfeffpeeffpfffefpppeffffpfeefpeeefppefefpfefepeffepefffppffeepefeepfeffpfeefppeefepfeefpefffpeefepppfeffpfeefffppfefepffeepffeepeeffppfefefpfeeeeppeeffpeeffpeeefpeeffpppfeefpfeffpfeeeeppefffpffefpffefpeeefpefpeffepfeefppffefpefffpeeffpfffeppppffeeepffefpfeeeppeeefpfffeepeeffppffefpfeffpefefpfeefppffeepefeepeffepeeefpppfeffpfffepfeefpffefppefefpefefpfeefpeefeppfeefpefffpeeefpfffeppfeffpeefepefeepfeeepppffefpeefeepfeefppefeefpffeepefefppefffpffefpeffepfefepepfefepeefepefffpppeeefpfeefpfffepeefeppfeeepfeefpefefpfffeppfeffpfeeepeefepeeefppfeefpfffepfefepefeeppppffefpefefpfffepfffeppfeefpefefpefeepefeeppefefepfeffpefffppefefpeeffpfefefppffpefffeppfeeepeffepfefefppeeffpfeeepefefpfeffppffeepfeeepfeeepfeeepppefeepffeffpefeeppffefpfeefpffeepeeffppeeffpefeepfefepeffeppeffepfeefpeefepfeffpppeffepefffpfffepffeeppfffepefeepeffepfeeeppefefpfeeepeefepeefeppfefepeeffpfffepfeffppppefeepeeffpffefpfefeppefefpefffpefeffppffeepefffpffeepeffeppfeffpefffpfefepefefpppffefpfeeepeeffpffeeppefffpefffpfeffpefefppefffpfefepfeeffppfefepfefepeefepeeefpppfefffpeeefpefffppfffeepeefepefffpepeeefpeeefpfeffppeeffpefffpefffpfefepppfeefpeffepefeepefeeppeffepfeeepefeepefeeppfeffpffeepfefeeppffeepeeefpffeee

The AC output is 788. Your code gives a seg fault when depth goes negative.