1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
|
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
const int IMAX = 7, JMAX = 8;
int A[IMAX][JMAX] = { { 5, 1, 0, 4, 1, 1, 2, 0 }, // Indexing orientation:
{ 0, 3, 2, 1, 0, 3, 0, 1 }, // +--------> j 0,0 -------- 0,JMAX-1
{ 4, 3, 0, 6, 5, 0, 1, 0 }, // | |
{ 3, 1, 0, 3, 4, 0, 1, 3 }, // | |
{ 0, 5, 2, 0, 1, 1, 5, 1 }, // | |
{ 2, 1, 6, 1, 6, 0, 2, 1 }, // \|/ |
{ 0, 0, 4, 3, 2, 3, 0, 2 } }; // i IMAX-1,0
for ( int d = 1; d <= IMAX + JMAX - 2; d++ ) // d is diagonal (= number of steps here)
{
for ( int j = max(0,d+1-IMAX), i = IMAX-1-d+j; j <= min(JMAX-1,d); i++, j++ )
{
if ( j == 0 ) A[i][j] += A[i+1][j];
else if ( i == IMAX - 1 ) A[i][j] += A[i][j-1];
else A[i][j] += max( A[i][j-1], A[i+1][j] );
}
}
cout << "Most gold is " << A[0][JMAX-1] << '\n';
}
|