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[i][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[i][j].first = true;
}
}
}
for (long i = 0; i < side; i++) {
for (long j = 0; j < side; j++) {
if (array[i][j].first && (i > 0 && !(array[i-1][j].first)) && (j > 0 && !(array[i][j-1].first))) {
array[i][j] = make_pair(false, array[i][j].second);
}
if (array[i][j].first) {
if (i > 0 && array[i-1][j].first) top = array[i-1][j].second;
else top = -1001 * 1001;
if (j > 0 && array[i][j-1].first) left = array[i][j-1].second;
else left = -1001 * 1001;
if (i == 0 && j == 0) top = 0;
array[i][j] = make_pair(true, max(top, left) + array[i][j].second);
}
}
}
/*
for (int i = 0; i < side; i++) {
for (int j = 0; j < side; j++) {
if (array[i][j].first) cout << "1 ";
else cout << "0 ";
}
cout << endl;
}
*/
if (array[side-1][side-1].first) cout << "YES\n" << array[side-1][side-1].second;
else cout << "NO\n";
return 0;
}
Please help. Thanks.