Programm mit rekursiver Funktion und ohne globale Variable - C++

Question

Ich habe ein Programm, das nach Pfad in 2-D-Array sucht, die "Kosten" ist die niedrigste. Hier ist ein Beispiel (Start: a [0] [2] -> Ende: a [3] [0]):

10 10 1 10 
10 10 1 10 
10 1 10 10 
0 10 10 10 

1 -> 1 -> 1 -> 0 

In meinem Fall muß ich aus Zeilennummer gehen 0 bis Zeilennummer 3 zu tun 3 Schritte (also drei Richtungen sind verfügbar). Sie können die Startnummer der Spalte auswählen.

Das Problem ist, ich kann das nicht tun, ohne globale Variable (min2) zu verwenden. Ich denke, ich sollte dann "int" nicht "void" rekursive Funktion verwenden.

Hier ist mein Code:

#include<iostream> 
#include<climits> 
using namespace std; 

int a[4][4] = {10, 10, 1, 10, 10, 10, 1, 10, 10, 1 ,10, 10, 0, 10, 10, 10}; 
int min2=INT_MAX; 
int k=2;   //column start number 

bool can_go(int x, int y){ 
    if(x<0 || x>3 || y<0 || y>3) 
     return false; 
    return true; 
} 

void min_path(int x, int y, int steps, int result){ 
    if(x==3 && steps==3){ 
     if(result<min2) 
      min2=result; 
    } 
    else{ 
     if(can_go(x+1,y)){ 
      min_path(x+1,y,steps+1,result+a[x+1][y]); 
     } 
     if(can_go(x+1,y-1)){ 
      min_path(x+1,y-1,steps+1,result+a[x+1][y-1]); 
     } 
     if(can_go(x+1,y+1)){ 
      min_path(x+1,y+1,steps+1,result+a[x+1][y+1]); 
     } 
    } 
} 

int go(){ 
    min_path(0,k,0,a[0][k]); 
    return min2; 
} 

int main(){ 
    cout << go(); 
} 

Answer 1

Es kann bei jeder Rekursion Aufruf den Minimalwert durch Rücksendung erfolgen. Die Vergleichsoperation wird dann in Nicht-Blatt-Knoten durchgeführt. Im ursprünglichen Code wird die Vergleichsoperation in Blattknoten durchgeführt (Basisfall). Die neue Funktion sieht so aus:

#include<iostream> 
#include<climits> 
using namespace std; 

int a[4][4] = {10, 10, 1, 10, 10, 10, 1, 10, 10, 1 ,10, 10, 0, 10, 10, 10}; 
int k=2;   //column start number 

bool can_go(int x, int y){ 
    if(x<0 || x>3 || y<0 || y>3) 
     return false; 
    return true; 
} 

int min_path(int x, int y, int steps, int result){ 
    if(x==3 && steps==3){ 
     return result; 
    } 
    else{ 
     int min = INT_MAX; 
     if(can_go(x+1,y)){ 
      int b = min_path(x+1,y,steps+1,result+a[x+1][y]); 
      if (b<min) 
       min=b; 
     } 
     if(can_go(x+1,y-1)){ 
      int b = min_path(x+1,y-1,steps+1,result+a[x+1][y-1]); 
      if (b<min) 
       min=b; 
     } 
     if(can_go(x+1,y+1)){ 
      int b = min_path(x+1,y+1,steps+1,result+a[x+1][y+1]);    
      if (b<min) 
       min=b; 
     } 
     return min; 
    } 
} 

int go(){ 
    return min_path(0,k,0,a[0][k]); 
} 

int main(){ 
    cout << go(); 
}