数组位置自动变为 1

Question

由于我已经发布了导致超出时间限制错误的 CodeForce 问题的可能解决方案 enter link description here，因此出现了一些解决方案。尽管如此，我还是找到了另一种解决方案..

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

现在没有导致超出时间限制，但它让我少了一个特定值的计数。

进一步调试，我发现对于 (1, 3) 的输入，代码不计算坐标 (2, 0)。

即使进行了进一步的调试，我发现 boxes[2][0] 在我实际手动将该坐标设为 1 之前就变成了 1。

示例输出如下所示

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

如您所见，第二个递归级别的 boxes[2][0] 变为 1，但 为什么？ 编辑

Answer 1

这部分我收到很多编译器警告

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

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

说 greatestY 不是常数。那么函数是如何知道数组大小的呢？

如果此时它接受 greatestY 作为大小，则数组将为 int boxes[][0]，并且所有访问将为 out-of-range。这肯定会产生意想不到的结果。

并且您传递的数组无论如何都不是那些维度，但是

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

Answer 2

感谢大家回答问题，看来问题出在将二维数组传递给函数。 gcc 没有抛出任何错误或警告，但 clang 给出了一些错误。因此我决定用 C++ 解决它。这是解决方案

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

数组位置自动变为 1

Array location is becoming 1 automatically

c

c99

multidimensional-array