qui hoạch động cơ bản: Tìm đường cho nhà khảo cổ...

// bài toán áp dụng qui hoạch động (mức cơ bản): Tìm đường cho nhà khảo cổ sao cho số đồ vật khai quật được là nhiều nhất,
// biết tại mỗi chỗ đứng nhà khảo cổ chỉ có 3 lựa chọn sau:
// 1 là hướng đông, 2 là hướng đông bắc, 3 là hướng đông nam
// input dòng đầu là số dòng (số cột) của ma trận, n dòng sau thể hiện ma trận,
// ô số 0 nghĩa là những nơi không thể tới,
// cột đầu tiên có duy nhất 1 ô giá trị 1 cho biết Start, (còn lại là 0)
// (những ô khác trên ma trận ngoại trừ 0 đều mang giá trị dương vì thể hiện số đồ vật được khai quật)
// output: vị trí bước đi của nhà khảo cổ

#include <iostream>
#include <iomanip>
#include <fstream>
#include <stack>
using namespace std;

int n=0;
int a[100][100];
int b[100][100];

int max3so(int x, int y, int z)
{
    int max1;
    if(x>y)
        max1=x;
    else
        max1=y;
    if(max1>z)
        return max1;
    else
        return z;
}

void main()
{
    ifstream fin;
    fin.open("input.txt");
    fin>>n;
    for(int i=0; i<n; i++)
    {
        a[n+1][i]=0;
        a[0][i]=0;
        b[n+1][i]=0;
        b[0][i]=0;
    }
    int i=0;
    int j=0;
    for(i=1; i<=n; i++)
    {
        for(j=0; j<n; j++)
        {
            {
                fin>>a[i][j];
                b[i][j]=a[i][j];
            }
        }
    }

    for(j=1; j< n; j++)
    {
        for(i=1; i<=n; i++)
        {
            {
                b[i][j]=max3so(b[i-1][j-1]+b[i][j],b[i+1][j-1]+b[i][j],b[i][j-1]+b[i][j]);
            }
        }
    }

    int max=0;
    for(i=1; i<=n; i++)
    {
        {
            if(b[i][n-1]>max)
                max=b[i][n-1];
        }
    }

    int k1 ;
    int k2 ;
    stack<int> st;

    for(i=1; i<=n; i++)
    {
        {
            if(b[i][n-1]==max)
            {
                //cout<<"("<<i-1<<","<<n-1<<")"<<endl;
                st.push(n-1);
                st.push(i-1);
                k1 = i;
                k2 = n-1;
                break;
            }
        }
    }

    int dem =0;
    while(dem!=n-1)
    {
        max-=a[k1][k2];
        for( i=1; i<=n; i++)
        {
            if((b[i][k2-1]==max)&&(i-1==k1||i+1==k1||i==k1))
            {
                //cout<<"("<<i-1<<","<<k2-1<<")"<<endl;
                st.push(k2-1);
                st.push(i-1);
                k2--;
                k1=i;
                dem++;
                break;
            }
        }
    }

    dem=0;
    while(!st.empty())
    {
        if(dem%2==0&&dem!=0)
            cout<<endl;
        cout<< st.top()<<" ";
        st.pop();
        dem++;
    }
    cout<<endl;
}