1

このプログラムは、左から右への最短経路の重みを 2 次元配列で返す必要があります (上と下をまたぐことができるため、水平の円柱のようなものです)。(ここに完全な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;
}
4

2 に答える 2

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;
}
于 2011-04-16T04:40:17.727 に答える
0

(コメントアウトした) rec_path() への最初の再帰呼び出しを行います。呼び出しが戻ると、c の値は 6 になります。次に、rec_path() への 2 回目の呼び出しで、呼び出しの前に 6 が 7 にインクリメントされます (つまり、++c)。現在、c は範囲外であり、障害の原因となっています。

于 2011-04-16T04:06:36.917 に答える