# PBinfo #1747 – Lacusta – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Enunț
Se consideră o matrice dreptunghiulară cu m linii şi n coloane, cu valori naturale. Traversăm matricea pornind de la colţul stânga-sus la colţul dreapta-jos. O traversare constă din mai multe deplasări. La fiecare deplasare se execută un salt pe orizontală şi un pas pe verticală. Un salt înseamnă că putem trece de la o celulă la oricare alta aflată pe aceeaşi linie, iar un pas înseamnă că putem trece de la o celulă la celula aflată imediat sub ea. Excepţie face ultima deplasare (cea în care ne aflăm pe ultima linie), când vom face doar un salt pentru a ajunge în colţul dreapta-jos, dar nu vom mai face şi pasul corespunzător. Astfel traversarea va consta din vizitarea a 2m celule. 

Cerinţă
Scrieţi un program care să determine suma minimă care se poate obţine pentru o astfel de traversare.

Date de intrare
Fișierul de intrare lacusta.in conține conţine pe prima linie două numere naturale separate printr-un spaţiu m n, reprezentând numărul de linii şi respectiv numărul de coloane ale matricei. Pe următoarele m linii este descrisă matricea, câte n numere pe fiecare linie, separate prin câte un spaţiu.

Date de ieșire
Fișierul de ieșire lacusta.out va conține pe prima linie suma minimă găsită.

Restricții și precizări

 1 ≤ m, n ≤ 100
Valorile elementelor matricei sunt numere întregi din intervalul [1,255]

Exemplu:
lacusta.in

4 5
3 4 5 7 9
6 6 3 4 4
6 3 3 9 6
6 5 3 8 2
lacusta.out

28
Explicație
Drumul este:
(1,1)->(1,3)->(2,3)->(2,2)->(3,2)->(3,3)->(4,3)->(4,5)

## Cod sursă C++

```cpp
#include <stdio.h>
#define M 100
int main()
{
  FILE *fi,*fo;
  unsigned int a[M][M],b[M][M],m,n,i,j,min1,min2,jmin;
  fi=fopen("lacusta.in", "rt");
  fscanf(fi,"%u %u", &m, &n);
  for(i=0; i<m; i++)
    for(j=0; j<n; j++)
      fscanf(fi,"%u",&a[i][j]);
  fclose(fi);
  b[1][0]=32000;
  for(i=1; i<n; i++)
    b[1][i]=a[0][0]+a[0][i]+a[1][i];
  for(i=1; i<m-1; i++)
    {
      if(b[i][0]<=b[i][1])
        {
          min1=b[i][0];
          min2=b[i][1];
          jmin=0;
        }
      else
        {
          min1=b[i][1];
          min2=b[i][0];
          jmin=1;
        }
      for(j=2; j<n; j++)
        if(b[i][j]<min1)
          {
            min2=min1;
            min1=b[i][j];
            jmin=j;
          }
		else
          if(b[i][j]<min2)
            min2=b[i][j];
      for(j=0; j<n; j++)
        if(j!=jmin)
          b[i+1][j]=min1+a[i][j]+a[i+1][j];
		else
          b[i+1][j]=a[i][j]+a[i+1][j]+min2;
    }
  min1=b[m-1][0];                       
  for (j=1; j<n; j++)                   
    if(b[m-1][j]<min1) min1=b[m-1][j];  
  fo=fopen("lacusta.out", "wt");
  fprintf(fo,"%u\n", min1+a[m-1][n-1]); 
  fclose(fo);
  return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1747)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1747/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1747/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)