Array location is becoming 1 automatically

Question

As a I have posted the possible solution to a CodeForce Problem which was causing Time Limit Exceed error posted enter link description here, some solutions came. Nevertheless I worked out with another solution..

#include <stdio.h>
#include <string.h>

int greatestX = 0, greatestY = 0;
int counter = 0;

void prune_boxes(int boxes[][greatestY], int x, int y){
  printf("boxes[2][0] = %d\n", boxes[2][0]);
  if (y < 0)
    return;
  else{
    //printf("x = %d y = %d\n", x, y);
    if (boxes[x][y] == 0){
      printf("x = %d y = %d\n", x, y);
      counter++;
      boxes[x][y] = 1;
    }
    prune_boxes(boxes, x, y - 1);
    prune_boxes(boxes, x + 1, y - 1);
  }
}


int main() {
  int wetBoxes, i, j;
  scanf("%d", &wetBoxes);
  int coordinates[wetBoxes][2];
  for(i = 0; i < wetBoxes; i++){
    scanf("%d%d", &coordinates[i][0], &coordinates[i][1]);
    if (coordinates[i][0] > greatestX)
      greatestX = coordinates[i][0];
    if (coordinates[i][1] > greatestY)
      greatestY = coordinates[i][1];
  }
  int boxes[greatestY + 1][greatestY + greatestX + 1];
  memset(boxes, 0, sizeof(boxes));
  /*
   for(i = 0; i < greatestY + 1; i++){
    for (j = 0; j < greatestY + greatestX + 1; j++){
      printf("%d ", boxes[i][j]);
    }
    printf("\n");
  }
  */

  for(i = 0; i < wetBoxes; i++){
    //printf("value = %d\n", boxes[coordinates[i][0]][coordinates[i][1]]);
    prune_boxes(boxes, coordinates[i][0], coordinates[i][1]);
  }
  printf("counter = %d\n", counter);

return 0;
}

Is not causing the the Time Limit Exceed now but it is giving me one less count of any particular value.

Debugging it further I found that for the input of (1, 3) the code is not counting the coordinate (2, 0).

Even with further debugging I found that boxes[2][0] is becoming 1 before I would actually make that coordinate 1 manually.

The sample output looks like this

1
1 3
boxes[2][0] = 0
x = 1 y = 3
boxes[2][0] = 1
x = 1 y = 2
boxes[2][0] = 1
x = 1 y = 1
boxes[2][0] = 1
x = 1 y = 0
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
x = 2 y = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
x = 3 y = 0
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
x = 2 y = 2
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
x = 3 y = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
boxes[2][0] = 1
x = 4 y = 0
boxes[2][0] = 1
boxes[2][0] = 1
counter = 9

As you can see that the boxes[2][0] from the second recursion level is becoming 1 but why ? Edit

Doesn't the compiler yell a warning at you passing to `prune_boxes() as 1st parameter something different as expected? — alk
– alk, Commented Jan 19, 2016 at 18:17
Yes it does...I find this is the most easiest way to pass a variable length array to a function in c99..can this be the cause of it?..moreover how you would pass vla to a function? — Mayukh Sarkar
– Mayukh Sarkar, Commented Jan 19, 2016 at 18:19
Use something like void foo(size_t x, size_t y, int p[x][y]);. Order matters. — alk
– alk, Commented Jan 19, 2016 at 18:23
Also take warnings serious and fix the code until they are gone. — alk
– alk, Commented Jan 19, 2016 at 18:23
gcc in c99 mode doesn't give any warning except the unused variable j...Moreover how passing x, y before p would make any difference ?? — Mayukh Sarkar
– Mayukh Sarkar, Commented Jan 19, 2016 at 18:29

Bo Persson · Accepted Answer · 2016-01-19 18:21:20Z

1

I get lots of compiler warnings for this part

int greatestX = 0, greatestY = 0;
int counter = 0;

void prune_boxes(int boxes[][greatestY], int x, int y){

saying that greatestY isn't a constant. So how is the function to know the size of the array?

If it accepts greatestYas the size at this point, the array would be int boxes[][0], and all accesses would be out-of-range. That surely can create unexpected results.

And the array you pass isn't of those dimensions anyway, but

int boxes[greatestY + 1][greatestY + greatestX + 1];

edited Jan 19, 2016 at 18:21

answered Jan 19, 2016 at 18:19

Bo Persson

92.9k31 gold badges153 silver badges211 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Mayukh Sarkar Over a year ago

How are you compiling..? are you using gcc -std=c99

Bo Persson Over a year ago

gcc accepts variable array sizes (VLA). I used MSVC, which does not. But anyway, you pass an array of a different size from what the function expects.

Mayukh Sarkar Over a year ago

Oh..but yes you are right..I passed the array of right size ( greatestY + greatestX + 1 ) and now it is counting 2, 0 but some other values are taken away..Is it because I passed the array wrongly in the function??

M.M Over a year ago

@MayukhSarkar you have to make sure the declared size of the array matches the array seen in the function signature... perhaps changing the function signature to int boxes[][greatestX + greatestY + 1] would fix

Mayukh Sarkar · Accepted Answer · 2016-01-19 21:36:36Z

Thanks folks for answering the question looks like the problem was passing the 2D array to the function. gcc was not throwing any error or warnings but clang was giving some error. Hence I decided to solve it in C++. Here is the solution

#include <iostream>
#include <vector>
#include <algorithm>

static int counter;
std::vector<std::vector<int>> boxes;
void prune_boxes(int x, int y){
 if (y < 0)
   return;
 else{
   if (boxes[x][y] == 0){
     boxes[x][y] = 1;
     counter++;
   }
   prune_boxes(x, y - 1);
   prune_boxes(x + 1, y - 1);
 }
}



int main(){
  int wetBoxes;
  std::cin >> wetBoxes;
  std::vector<int> coordinatesX;
  std::vector<int> coordinatesY;
  int input;
  for (int i = 0; i < wetBoxes; i++){
    std::cin >> input;
    coordinatesX.push_back(input);
    std::cin >> input;
    coordinatesY.push_back(input);
  }

  int greatestX = *max_element(coordinatesX.begin(), coordinatesX.end());
  int greatestY = *max_element(coordinatesY.begin(), coordinatesY.end());

  int Y =  greatestY + 1;
  int X =  greatestX + greatestY + 1;
  boxes.resize(X);
  for (int i = 0; i < X; i++){
    for (int j = 0; j < Y; j++){
      boxes[i].push_back(0);
    }
  }

  for(int i = 0; i < wetBoxes; i++){
    prune_boxes(coordinatesX[i], coordinatesY[i]);
    std::cout << counter << std::endl;
    counter = 0;
  }
  return 0;
}

Collectives™ on Stack Overflow

Array location is becoming 1 automatically

2 Answers 2

4 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Related