2-dimensionale Array in "Edit Abstand" auf spoj lokal gibt Laufzeitfehler?

Question

Während http://www.spoj.com/problems/EDIST/ lösen, wenn ich die 2-D-Array global deklarieren: (http://ideone.com/jG3jPW)

#include <iostream> 
using namespace std; 

long long int s[2001][2001]; 

int main() { 
int t; 
string a,b; 
long long int i,j; 
for(i=0;i<2001;i++) 
{ 
    s[i][0]=i; 
    s[0][i]=i; 
} 
cin>>t; 
while(t>0) 
{ 
    cin>>a>>b; 
    t--; 
    for(i=1;i<=a.length();i++) 
    { 
     for(j=1;j<=b.length();j++) 
     { 
      if(a[i-1] == b[j-1]) 
       s[i][j]=s[i-1][j-1]; 
      else 
       s[i][j] = min(min(s[i-1][j],s[i-1][j-1]),s[i][j-1]) + 1; 
     } 
    } 
    cout<<s[i-1][j-1]<<"\n"; 
} 
return 0; 
} 

kein Fehler auftritt. Aber wenn ich das gleiche Array deklarieren lokal (http://ideone.com/Tyj6UU),

#include <iostream> 
using namespace std; 


int main() { 
int t; 
string a,b; 
long long int i,j; 

long long int s[2001][2001]; //declared locally 

for(i=0;i<2001;i++) 
{ 
    s[i][0]=i; 
    s[0][i]=i; 
} 
cin>>t; 
while(t>0) 
{ 
    cin>>a>>b; 
    t--; 
    for(i=1;i<=a.length();i++) 
    { 
     for(j=1;j<=b.length();j++) 
     { 
      if(a[i-1] == b[j-1]) 
       s[i][j]=s[i-1][j-1]; 
      else 
       s[i][j] = min(min(s[i-1][j],s[i-1][j-1]),s[i][j-1]) + 1; 
     } 
    } 
    cout<<s[i-1][j-1]<<"\n"; 
} 
return 0; 
} 

Laufzeitfehler. Warum?

Answer 1

Es scheint, dass Sie ein Problem mit der Speicherzuweisung haben.

In Ihrem zweiten Ansatz (das heißt, das mit lokaler Deklaration), Änderung:

long long int s[2001][2001]; 

An:

long long int ** s = new long long int * [2001]; 
for (i=0;i<2001;i++) 
    s[i] = new long long int[2001]; 

Dies wird Ihr Problem lösen.