Maksimalna suma uz rupe na putu kroz matricu

U tabeli dimenzija \(n \times n\) svako polje sadrži cifru od 1 do 9 ili cifru 0 (rupa). Igrač se nalazi u gornjem levom polju i u svakom koraku može da pređe u susedno desno ili susedno donje polje. Polja označena sa 0 su nedostupna i ne smeju se posećivati. Cilj je da se stigne do donjeg desnog polja tako da zbir vrednosti na posećenim poljima bude maksimalan.

Napisati program kojim se određuje maksimalan zbir koji može da ostvari igrač pri kretanju od gornjeg levog do donjeg desnog ugla. Pored toga, program treba i da detektuje ukoliko put ne postoji.

Za maksimalno poena rešiti zadatak u optimalnoj vremenskoj složenosti i konstantnoj dodatnoj memorijskoj složenosti.

Opis ulaza

Sa standardnog ulaza unosi se ceo broj \(n\) (\(1 \leq n \leq 120\)). U sledećih \(n\) redova nalazi se po \(n\) tokena razdvojenih jednim razmakom; svaki token je ili:

Početno (gornje levo) i završno (donje desno) polje takođe mogu biti 0.

Opis izlaza

Ako ne postoji dozvoljen put od gornjeg levog do donjeg desnog polja (koji ne staje na 0), na standardni izlaz ispisati NEMA. Inače, na standardni izlaz ispisati maksimalnu moguću sumu cifara na putu (računajući i početno i završno polje).

Primer 1

Ulaz

5
4 3 0 7 5
1 9 4 1 3
2 3 5 0 2
1 0 1 2 0
4 6 7 2 1

Izlaz

36

Objašnjenje

Obajašnjenje

Maksimalni zbir se dobija kada se redom prelaze polja sa vrednošću \(4+3+9+4+5+1+7+2+1=36\).

Primer 2

Ulaz

5
4 0 0 7 5
1 0 4 1 3
2 0 5 0 2
1 0 0 0 0
4 6 7 0 1

Izlaz

NEMA

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <iostream>
#include <limits>
#include <vector>

using namespace std;

#define NEG_INF (numeric_limits<int>::min())

int plus_NEG_INF(int x, int y)
{
    if (x != NEG_INF && y != NEG_INF) {
        return x + y;
    } 

    return NEG_INF;
}

int max_path(const vector<vector<int>> &M, const int i, const int j,
             vector<vector<int>> memo)
{
    if (memo[i][j]) {
        return memo[i][j];
    }

    if (i == 0 && j == 0) {
        return memo[i][j] = M[i][j];
    }
    
    if (i == 0) {
        return memo[i][j] = plus_NEG_INF(M[i][j], max_path(M, i, j - 1, memo));
    }

    if (j == 0) {
        return memo[i][j] = plus_NEG_INF(M[i][j], max_path(M, i - 1, j, memo));
    }

    return memo[i][j] = plus_NEG_INF(M[i][j], max(max_path(M, i - 1, j, memo), max_path(M, i, j - 1, memo)));
}

int max_path(vector<vector<int>> &M)
{
    const int n = M.size();

    for (int i = 1; i < n; i++) {
        M[i][0] = plus_NEG_INF(M[i][0], M[i - 1][0]);
    }

    for (int j = 1; j < n; j++) {
        M[0][j] = plus_NEG_INF(M[0][j], M[0][j - 1]);
    }

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            M[i][j] = plus_NEG_INF(M[i][j], max(M[i - 1][j], M[i][j - 1]));
        }
    }

    return M[n - 1][n - 1];
}

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

    vector<vector<int>> M(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int v; cin >> v;
            if (v == 0) {
                M[i][j] = NEG_INF;
            } else {
                M[i][j] = v;
            }
        }
    }

    int res = max_path(M);

    if (res != NEG_INF) {
        cout << res << endl;
    } else {
        cout << "NEMA" << endl;
    }

    return 0;
}
#include <iostream>
#include <limits>
#include <vector>

using namespace std;

#define NEG_INF (numeric_limits<int>::min())

int plus_NEG_INF(int x, int y)
{
    if (x != NEG_INF && y != NEG_INF) {
        return x + y;
    } 

    return NEG_INF;
}

int max_path(const vector<vector<int>> &M, const int i, const int j)
{
    if (i == 0 && j == 0) {
        return M[0][0];
    }
    
    if (i == 0) {
        return plus_NEG_INF(M[i][j], max_path(M, i, j - 1));
    }

    if (j == 0) {
        return plus_NEG_INF(M[i][j], max_path(M, i - 1, j));
    }

    return plus_NEG_INF(M[i][j], max(max_path(M, i - 1, j), max_path(M, i, j - 1)));
}

int max_path(const vector<vector<int>> &M)
{
    const int n = M.size();
    return max_path(M, n - 1, n - 1);
}

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

    vector<vector<int>> M(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int v; cin >> v;
            if (v == 0) {
                M[i][j] = NEG_INF;
            } else {
                M[i][j] = v;
            }
        }
    }

    int res = max_path(M);

    if (res != NEG_INF) {
        cout << res << endl;
    } else {
        cout << "NEMA" << endl;
    }

    return 0;
}
#include <iostream>
#include <limits>
#include <vector>

using namespace std;

#define NEG_INF (numeric_limits<int>::min())

int plus_NEG_INF(int x, int y)
{
    if (x != NEG_INF && y != NEG_INF) {
        return x + y;
    } 

    return NEG_INF;
}

int max_path(const vector<vector<int>> &M, const int i, const int j,
             vector<vector<int>> memo)
{
    if (memo[i][j] != 0) {
        return memo[i][j];
    }

    if (i == 0 && j == 0) {
        return memo[i][j] = M[i][j];
    }
    
    if (i == 0) {
        return memo[i][j] = plus_NEG_INF(M[i][j], max_path(M, i, j - 1, memo));
    }

    if (j == 0) {
        return memo[i][j] = plus_NEG_INF(M[i][j], max_path(M, i - 1, j, memo));
    }

    return memo[i][j] = plus_NEG_INF(M[i][j], max(max_path(M, i - 1, j, memo), max_path(M, i, j - 1, memo)));
}

int max_path(const vector<vector<int>> &M)
{
    const int n = M.size();
    vector<vector<int>> memo(n + 1, vector<int>(n + 1));
    return max_path(M, n - 1, n - 1, memo);
}

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

    vector<vector<int>> M(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int v; cin >> v;
            if (v == 0) {
                M[i][j] = NEG_INF;
            } else {
                M[i][j] = v;
            }
        }
    }

    int res = max_path(M);

    if (res != NEG_INF) {
        cout << res << endl;
    } else {
        cout << "NEMA" << endl;
    }

    return 0;
}
#include <iostream>
#include <limits>
#include <vector>

using namespace std;

#define NEG_INF (numeric_limits<int>::min())

int plus_NEG_INF(int x, int y)
{
    if (x != NEG_INF && y != NEG_INF) {
        return x + y;
    } 

    return NEG_INF;
}

int max_path(const vector<vector<int>> &M, const int i, const int j,
             vector<vector<int>> memo)
{
    if (memo[i][j]) {
        return memo[i][j];
    }

    if (i == 0 && j == 0) {
        return memo[i][j] = M[i][j];
    }
    
    if (i == 0) {
        return memo[i][j] = plus_NEG_INF(M[i][j], max_path(M, i, j - 1, memo));
    }

    if (j == 0) {
        return memo[i][j] = plus_NEG_INF(M[i][j], max_path(M, i - 1, j, memo));
    }

    return memo[i][j] = plus_NEG_INF(M[i][j], max(max_path(M, i - 1, j, memo), max_path(M, i, j - 1, memo)));
}

int max_path(const vector<vector<int>> &M)
{
    const int n = M.size();

    vector<vector<int>> dp(n + 1, vector<int>(n + 1));

    dp[0][0] = M[0][0];

    for (int i = 1; i < n; i++) {
        dp[i][0] = plus_NEG_INF(M[i][0], dp[i - 1][0]);
    }

    for (int j = 1; j < n; j++) {
        dp[0][j] = plus_NEG_INF(M[0][j], dp[0][j - 1]);
    }

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = plus_NEG_INF(M[i][j], max(dp[i - 1][j], dp[i][j - 1]));
        }
    }

    return dp[n - 1][n - 1];
}

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

    vector<vector<int>> M(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int v; cin >> v;
            if (v == 0) {
                M[i][j] = NEG_INF;
            } else {
                M[i][j] = v;
            }
        }
    }

    int res = max_path(M);

    if (res != NEG_INF) {
        cout << res << endl;
    } else {
        cout << "NEMA" << endl;
    }

    return 0;
}