Cerinţa

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. În fiecare cameră se află o cantitate cunoscută de bomboane. Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j+1), fără a părăsi clădirea.

Un copil intră în clădire, parcurge un șir de camere după regula precizată și iese din clădire, luând din fiecare cameră în care intră toate bomboanele existente. Determinați cantitatea maximă de bomboane care poate fi culeasă precum și un traseu prin clădire în care se adună cantitatea maximă de bomboane.

Date de intrare

Fişierul de intrare cladire2.in conţine pe prima linie numerele n m. Fiecare dintre următoarele n linii conține câte m numere, reprezentând cantitățile de bomboane camerele date.

Date de ieşire

Fişierul de ieşire cladire2.out va conţine pe prima linie numărul B, cantitatea maximă de bomboane care pot fi adunate. Pe următoarele n+m-1 linii se află câte două numere i j reprezentănd, în ordine, coordonatele camerelor din care se adună bomboanele.

Restricţii şi precizări

• 1 ≤ n , m ≤ 200;
• în fiecare cameră se află cel puțin una și cel mult 100 de bomboane.

Exemplu

cladire2.in

3 4
1 1 5 2  
3 2 7 1
1 1 8 2

cladire2.out

24
1 1
1 2
1 3
2 3
3 3
3 4

Explicație

Numărul maxim de bomboane se obține: 24 = 1 + 1 + 5 + 7 + 8 + 2, parcurgând camerele descrise mai sus.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("cladire2.in");
ofstream cout("cladire2.out");

int n , m , a[201][201] , cnt , s[201][201];

struct poz
{
    int i , j;
}rez[401];

int main()
{
    cin >> n >> m;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            cin >> a[i][j];

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            s[i][j] = a[i][j] + max(s[i - 1][j] , s[i][j - 1]);

    cout << s[n][m] << '\n';

    int i = n , j = m;

    while(s[i][j] - a[i][j] != 0)
    {
        rez[cnt].i = i , rez[cnt].j = j;
        cnt++;
        if(s[i][j - 1] == s[i][j] - a[i][j]) j--;
        else i--;
    }

    cout << "1 1" << '\n';
    for(int i = cnt - 1 ; i >= 0 ; i--)
        cout << rez[i].i << " " << rez[i].j << '\n';

    return 0;
}