ZCO Little Red Riding Hood - Error in 1 test case

2darray
debugging
dynamic-programming
test-cases
zco

#1

I am solving the ZCO Contest - Little Red Riding Hood problem. The code I’ve written works correctly for all test cases except one - the case no. 6. I am not able to realize the error.

My approach is a simple DP approach.

Please help in debugging my code.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

// ZCO13002 ZCO13002 ZCO13002 ZCO13002 ZCO13002 ZCO13002

int main() {
    long long side, protections, number;
    cin >> side >> protections;

    pair<bool, long> array[500][500];

    for (long i = 0; i < side; i++) {
        for (long j = 0; j < side; j++) {
            cin >> number;
            array*[j] = make_pair(false, number);
        }
    }

    long long x, y, strength, top, left, zero = 0;
    for (long i = 0; i < protections; i++) {
        cin >> x >> y >> strength;
        x--;
        y--;

        for (long i = max(x - strength, zero); i <= min(side-1, x+strength); i++) {
            for (long j = max(y - strength, zero); j <= min(side-1, y+strength); j++) {
                if (abs(x-i) + abs(y-j) <= strength) array*[j].first = true;
            }
        }
    }

    for (long i = 0; i < side; i++) {
        for (long j = 0; j < side; j++) {
            if (array*[j].first && (i > 0 && !(array[i-1][j].first)) && (j > 0 && !(array*[j-1].first))) {
                array*[j] = make_pair(false, array*[j].second);
            }

            if (array*[j].first) {
                if (i > 0 && array[i-1][j].first) top = array[i-1][j].second;
                else top = -1001 * 1001;

                if (j > 0 && array*[j-1].first) left = array*[j-1].second;
                else left = -1001 * 1001;

                if (i == 0 && j == 0) top = 0;

                array*[j] = make_pair(true, max(top, left) + array*[j].second);
            }
        }
    }

    /*
    for (int i = 0; i < side; i++) {
        for (int j = 0; j < side; j++) {
            if (array*[j].first) cout << "1 ";
            else cout << "0 ";
        }
        cout << endl;
    }
    */

    if (array[side-1][side-1].first) cout << "YES

" << array[side-1][side-1].second;
else cout << "NO
";

    return 0;
}

Please help. Thanks.


#2

Please help me with this one.