Knight move, right direction, dynamic programming to get the maximum cost path from top left to right bottom.

[Jiopik]

I am trying to solve this problem through dynamic programming: You are given a matrix of n rows and m columns. There’s an integer number on each cell of the board and the rabbit staying at the upper-left corner. Collect the greatest sum possible, such that the rabbit can move in only two directions: 2 cells to the right and 1 cell down (x+2, y+1); 2 cells down and 1 cell to the right (x+1, y+2); Input: The first line contains two naturals n and m (1 ≤ n, m ≤ 10^3) – the quantity of rows and columns of the matrix. The next n lines contain m numbers – the values of the matrix elements. The upper-left corner’s coordinates are (1, 1), the lower-right corner’s – (n, m). Output: The greatest sum possibly collected. If the r rabbit can’t reach the lower-right corner, output «-». Input1: 3 3 5 0 0 0 1 2 1 0 1 Output1: - Input2: 4 4 5 2 1 0 1 0 0 0 2 1 3 0 0 0 1 7 Output2: 13 This the code I tried to develop:

#include
//#include
//#include
//#include
#include

using namespace std;
void findMaxSum(int *a[], int r, int c)
{

int \*\*res = new int\*\[r\];
for (int i = 0; i < r; i++) {
    res\[i\] = new int\[c\];
    for (int j = 0; j < c; j++)
        res\[i\]\[j\] = -1;
}

for (int i = 0; i < r-1; i++) {
    for (int j = i; j < c-1; j++) {
        res\[i + 1\]\[j + 2\] = max(a\[i\]\[j\] + a\[i + 1\]\[j + 2\], res\[i + 1\]\[j + 2\]);
        res\[i + 2\]\[j + 1\] = max(a\[i\]\[j\] + a\[i + 2\]\[j + 1\], res\[i + 2\]\[j + 1\]);
    }
}

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++)
        cout << res\[i\]\[j\] << " ";
    cout << endl;
}
delete\[\] res;

/\*int result = res\[r - 1\]\[c - 1\];
if (result == -1)
    cout << "-";
else
    cout << result;\*/

}

int main() {

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int r, c;
cin >> r >> c;

int \*\*a = new int\*\[r\];

for (int i = 0; i < r; i++) {
    a\[i\] = new int\[c\];
}

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++)
        cin >> a\[i\]\[j\];
}


findMaxSum(a, r, c);
delete\[\] a;
return 0;

}

Could you help which right for or while loop to use to calculate such sum?

[Lost User]

the knight problem - Google Search[^]