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超出了导致故障的范围。