Question

Ali Baba și cei 40 de hoți stăpânesc un deșert de formă dreptunghiulară, împărțit în n linii și m coloane, care definesc n*m sectoare. Intrarea într-un sector se plătește cu o taxă cunoscută, exprimată în galbeni. Un călător trebuie să traverseze deșertul de la Est la Vest, trecând dintr-un sector în altul, astfel: din sectorul (i j) se poate ajunge în unul din sectoarele (i-1,j-1), (i,j-1) sau (i+1,j-1), dar fără a părăsi deșertul (ar fi omorât de oamenii lui Ali Baba). La trecerea printr-un sector, călătorul plătește taxa aferentă acelui sector. Determinați suma totală minimă pe care trebuie să o plătească călătorul la traversarea deșertului, știind că pleacă din orice sector al coloanei m (Est) și se oprește în orice sector al coloanei 1 (Vest), cu respectarea condițiilor de mai sus.

Answer 1

#include <iostream>
using namespace std;

int a[200][200];
int b[200][200];

int main() {

    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        cin >> a[i][j];   
    for(int i = 0 ; i < n; i++)
      b[i][0] = a[i][0];
    for(int j = 1; j < m; j++) {
      b[0][j] = a[0][j] + min(b[0][j - 1], b[1][j - 1]);
      for (int i = 1; i + 1 < n; i++)
        b[i][j] = a[i][j] + min(min(b[i - 1][j - 1], b[i][j - 1]), b[i + 1][j - 1]);
      b[n - 1][j] = a[n - 1][j] + min(b[n - 2][j - 1], b[n - 1][j - 1]);
    }
    int sol = b[0][m - 1];
    for(int i = 1; i < n; i++)
      sol = min(sol, b[i][m - 1]);
    cout << sol;
    return 0;
}