CODEWITHSUNDEEP
c++recursion
sclee1
sclee1

Reputation: 1281

Recursive function program - find the route that maximizes the sum of values in two dimension arrays

I am trying to find the path in two dimension arrays in order to get the maximal value that is the summation of each value in the path.

For example, here is my two array as below.

6 0 0
1 2 0
6 7 4

Starting at the (0,0) and find the path that has the maximal summation value. (Path can be directed into only two ways as follows, if a current point is (y,x) then, next path can be (y+1,x) or (y+1,x+1)).

After applying above procedure, the converted dimension arrays will be as follows:

6 0 0      15 0 0   
8 9 0  ->  8 9 0  
6 7 4      6 7 4

Therefore, the solution is 15. And I tried to make a code using recursive function as below.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stdio.h>
#include <map>

using namespace std;

namespace DIAMONDPATH {
    int dia[2 * 100][100];
    int copy_dia[2 * 100][100];

    int path(int y, int x,int height) {
        if (height == y + 1) {
            return dia[y][x];
        }

        copy_dia[y][x] = max(dia[y][x]+path(y + 1, x,height), dia[y][x]+path(y + 1, x + 1,height));

        cout << "y : "<<y<<" x : "<<x<<" value : "<< copy_dia[y][x] << endl;
    }
    int do_main(int argc, const char *argv[]) {
        freopen("input.txt", "r", stdin);

        int TC;
        cin >> TC;

        while (TC--) {
            int N;
            cin >> N;

            memset(copy_dia, -1, sizeof(copy_dia));
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j <= i; ++j) {
                    cin >> dia[i][j];
                }
            }


            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N ; ++j) {
                    cout << dia[i][j] << " ";
                }
                cout << endl;
            }




            int ret = path(0, 0,N);



            cout << endl;

        }
        return 0;
    }
}

#ifndef DRIVER

int main(int argc, const char *argv[]) {
    return DIAMONDPATH::do_main(argc, argv);
}

#endif

However, I ran my codes, the final results (the position of (0,0)) is not the value what I intended. It returned unknown value. I couldn't know where it came from.

As you can see, path function is the getting the maximal value of optimal path in my arrays. and I inputted the 3x3 dimension arrays as below.

6 0 0
1 2 0
6 7 4

I tried to debug using printf but I failed because it was recursive and very hard to understand and see each procedure. Therefore I posted my problems here and would like to know how to debug it and where did the unknown value came from ?

Thanks.

Upvotes: 0

Views: 124

Answers (1)

max66
max66

Reputation: 66200

Your path() doesn't return the value (that is: return an undefined value) when height != y+1; suggestion: add a return instruction like 

int path(int y, int x,int height) {
    if (height == y + 1) {
        return dia[y][x];
    }

    copy_dia[y][x] = max(dia[y][x]+path(y + 1, x,height), dia[y][x]+path(y + 1, x + 1,height));

    cout << "y : "<<y<<" x : "<<x<<" value : "<< copy_dia[y][x] << endl;

    return copy_dia[y][x];  //  <-----  add return
}

Upvotes: 1

Related Questions