297 - Quadtrees

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

297 - BUG?

Post 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

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post 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:

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

297 - BUG?

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

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

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

Post 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
Last edited by Red Scorpion on Fri Mar 21, 2003 10:12 am, edited 1 time in total.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion »

Ignore this I've got AC.
Thanks,
RS :lol: :lol: :lol: :lol:

Syeed
New poster
Posts: 1
Joined: Sun Nov 09, 2003 5:17 am
Location: Dhaka
Contact:

297 !!

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

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

try this case:

1
f
f

ans should be 1024

Yaron Wittenstein
New poster
Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm
Contact:

Quadtrees (Problem 297): I get Output Limit Exceeded

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

Yaron Wittenstein
New poster
Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm
Contact:

Quadtrees (Problem 297): I get Output Limit Exceeded

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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by 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
New poster
Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm
Contact:

It works now, I got AC thank!!!

Post by Yaron Wittenstein »

Thank you very much!!

zenden
New poster
Posts: 2
Joined: Tue Mar 29, 2005 12:14 am

297 QuadTree WA HELP! GOING INSANE!

Post 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:

zenden
New poster
Posts: 2
Joined: Tue Mar 29, 2005 12:14 am

Post by zenden »

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

883030721
New poster
Posts: 1
Joined: Sat Jun 16, 2012 11:53 pm

297 Quadtrees(Runtime error)

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 297 Quadtrees(Runtime error)

Post by brianfry713 »

Input:

Code: Select all

1
pppppfefepffefpeeffpfffeppffefpffeepfeefpfeffppeeefpfefepefffpfeeeppefefpfeefpffeepfefepppeeffpeefepfffepfffeppeefepefffpeefepffefpfpffefpefefpffeeppffefpfeeepefefeppfpfeefpfefeeppeffepfefepfeeepfefeppfefepefefpeeeffppeffepffeepfffepeefepppfeefpefeepefefpfeeeppeeefpfeffpefeffppffefpfefepeeffpfeeeppfffepefeepfefepffefppppfffefpffeffpfpfeefpeeefpfffepfpffefpefffpfefeppefeepeefepefffpffefpppfeefpffeeepefefppfeffffpefffppeefepefffpefffpeeefppeeffepefefpeffepppfeefpfffepfeeepefffpfpeeffpffeepffeeppffeepfeffpfeffpefefppefeffpffeepefffpppefeefpfefepeefeppffeepeffepeeffpeeffppefeepeeefpeefepeeffppefeepefffpfefepefeepppepfefepfeefpfeffppeeefpeefepeeefpffefppeeefpfffepffeepeefeppeeffpfefepffefpeeffpppeffepfeeefpeeffppffefpfeffpffefpffefppfeffpeeffpeefepeefeppfefepeeefpeefepfeefpppeeefpeeefpeeffpffeeppfffepfeeepffeepefefppfefepeeefepeefeppeeffpeffepfeefpefefpppeffepfeffpfeeepffefppfeefpfefepeeefpeefeppeefepfefepffeepeeefppefeepffefepffefppppeeefpfeffpfeeepfeefppefffpfeffpfeefpfefeppeeffpeeffpfeffpeeefppffefpfeefpfeffpeffepppffeepefeepefefpeeefppeeffpefffpeffepfffeppfeefpfefepfeeepeeefppeeffpfffepffeepeefepppfeeepefefpeeefpfeffppffeepefffpeefepfeeeppfffepeeffffppeeffpeeffpffefpfeeepppeefepeefepffefpfeffpfpffeeffpepefefpfeefpffefpfpffeepffeepfffe
pppppfefepfeffpeefepeeefppfeefpfefepffeepffefppfeffpefefpeeefpfefeppfeffpeeffpfffefpppeffffpfeefpeeefppefefpfefepeffepefffppffeepefeepfeffpfeefppeefepfeefpefffpeefepppfeffpfeefffppfefepffeepffeepeeffppfefefpfeeeeppeeffpeeffpeeefpeeffpppfeefpfeffpfeeeeppefffpffefpffefpeeefpefpeffepfeefppffefpefffpeeffpfffeppppffeeepffefpfeeeppeeefpfffeepeeffppffefpfeffpefefpfeefppffeepefeepeffepeeefpppfeffpfffepfeefpffefppefefpefefpfeefpeefeppfeefpefffpeeefpfffeppfeffpeefepefeepfeeepppffefpeefeepfeefppefeefpffeepefefppefffpffefpeffepfefepepfefepeefepefffpppeeefpfeefpfffepeefeppfeeepfeefpefefpfffeppfeffpfeeepeefepeeefppfeefpfffepfefepefeeppppffefpefefpfffepfffeppfeefpefefpefeepefeeppefefepfeffpefffppefefpeeffpfefefppffpefffeppfeeepeffepfefefppeeffpfeeepefefpfeffppffeepfeeepfeeepfeeepppefeepffeffpefeeppffefpfeefpffeepeeffppeeffpefeepfefepeffeppeffepfeefpeefepfeffpppeffepefffpfffepffeeppfffepefeepeffepfeeeppefefpfeeepeefepeefeppfefepeeffpfffepfeffppppefeepeeffpffefpfefeppefefpefffpefeffppffeepefffpffeepeffeppfeffpefffpfefepefefpppffefpfeeepeeffpffeeppefffpefffpfeffpefefppefffpfefepfeeffppfefepfefepeefepeeefpppfefffpeeefpefffppfffeepeefepefffpepeeefpeeefpfeffppeeffpefffpefffpfefepppfeefpeffepefeepefeeppeffepfeeepefeepefeeppfeffpffeepfefeeppffeepeeefpffeee
The AC output is 788. Your code gives a seg fault when depth goes negative.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 2 (200-299)”