再帰関数とグローバル変数を持たないプログラム - C++

Question

"コスト"が最も低い2次元配列のパスを探すプログラムがあります。ここでは一例です（開始：[0] [2] - > [エンドを：[3] [0]）：私の場合は

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

1 -> 1 -> 1 -> 0 

、私がやって数3の行に行番号0から行く必要があります3ステップ（3つの方向があります）。列の開始番号を選択できます。

問題はグローバル変数（min2）を使用しないとできないということです。私は "int"を "void"再帰関数ではなく使うべきだと思います。

#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

それはリターンすることにより、各再帰呼び出しでの最小値を行うことができます。

は、ここに私のコードです。比較操作は、非リーフノードで行われます。元のコードでは、比較操作はリーフノード（ベースケース）で行われます。新しい関数は次のようになります。

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