C++遞歸找到水平圓柱體中的最短路徑（遞歸問題）

Question

該程序應該從左到右返回最短路徑的權重（它也可以超過頂部和底部，所以它就像一個水平圓柱體）在二維數組中（這裏是一個完整的question_link） 我試圖通過首先向上檢查，然後右對齊，最後在數組中進行遞歸檢查。 通過運行這個程序，我得到了「分段錯誤」，如果我取消註釋線的正確方向和底部方向。 如果任何人都可以告訴我我在做遞歸函數時做錯了什麼。提前致謝！

#include<iostream> 
using namespace std; 

int rec_path(int matrix[5][6], int r, int c){ 
static int sum = 0; 
static int weight = -1; 
    if (r == -1) 
    r = 4; 

if (r == 5) 
    r = 0; 

if (c == 6) { 
    return weight; 
    sum = 0; 
} 
//calculate sum 
sum += matrix[r][c];  
//check the up direction 
rec_path(matrix, --r, ++c); 
//check the right direction 
// rec_path(matrix, r, ++c); 
//check the bottom direction 
// rec_path(matrix, ++r, ++c); 
if (weight == -1) 
    weight = sum; 
if (weight < sum) { 
    weight = sum; 
} 
} 


int main(){ 
const int row = 5; 
const int col = 6; 
int matrix[row][col] = {{3,4,2,1,8,6}, 
         {6,1,8,2,7,4}, 
         {5,9,3,9,9,5}, 
         {8,4,1,3,2,6}, 
         {3,7,2,8,6,4} 
         }; 

cout << rec_path(matrix,0,0) << endl; 
return 0; 
} 

Answer 1

在這裏，你去。這隻會返回路徑的成本，找到實際的路徑只是對這個簡單的修改 。

int rec_path(int matrix[5][6],int r,int c,int cost) 
{ 
    if(c==6) return cost; 
    int ans=2e9; 
    static const int dr[]={-1,0,1}; 
    for(int i=0;i<3;i++) 
     ans=min(ans,rec_path(matrix,(5+(r+dr[i])%5)%5,c+1,cost+matrix[r][c])); 
    return ans; 
} 

Answer 2

在第一個遞歸調用rec_path（）（已註釋掉）。一旦調用返回，c的值爲6.然後，在第二次調用rec_path（）時，在調用之前，6會增加到7（即++ c）。現在c超出了導致故障的範圍。