About the problem that the two-dimensional array is too large to explode the stack

About the problem that the [two-dimensional array] is too large to “explode the stack”

Today, when I was working on a [shortest path] algorithm with a graph ( https://pintia.cn/problem-sets/15/problems/717 ), I encountered this problem for the first time.

The code block is as follows:

int main(){
    int N,M,S,D ;
    cin >> N >> M >> S >> D ;
    int Graph[510][510] = {0} ;
    int Money[510][510] = {0} ;
    for(int i=0;i<510;i++)
      for(int j= 0;j<510;j++){
        if(i != j){
            Graph[i][j] = MaxDist ;
            Money[i][j]  = MaxDist ;
          }
      }
      ............

When I run it, this situation occurs directly:
that is: without input, the program ends directly.
After several attempts, it was found that the array was enlarged by 510, which actually exploded the stack. . .

The reason is also very simple, my program shows that I open a local variable instead of a global variable (the main function is also a function, and it is also a local variable in the main function), so my array is opened. The local variable on the stack is It is placed in the stack, and the space of the stack is often relatively small, which involves the problem of limiting the size of the stack at compile time, so the stack is burst.

The solution is to set the variable to a global variable or a static global variable or, (of course, you can also manually modify the size of the stack). as follows:

int Graph[510][510] = {0} ;
int Money[510][510] = {0} ;
int main(){
    int N,M,S,D ;
    cin >> N >> M >> S >> D ;

    for(int i=0;i<510;i++)
      for(int j= 0;j<510;j++){
        if(i != j){
            Graph[i][j] = MaxDist ;
            Money[i][j]  = MaxDist ;
          }
      }

This will work fine:

However, when submitting directly on the PTA, it is no problem to directly set the two-dimensional array (local variable) to 500*500. How big is their stack?

Leave a Comment

Your email address will not be published. Required fields are marked *