# PBinfo #3702 – npath – Rezolvare C++

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

## Enunț

Fie N și K două numere naturale. Toate punctele din plan de coordonate întregi (x,y) cu proprietatea 0 ≤ x ≤ N, 0 ≤ y ≤ N se unesc prin linii orizontale și verticale de lungime 1. Apoi K linii de lungime 1 dintre cele de mai sus se șterg. Definim o cale ca fiind o succesiune continuă de linii orizontale sau verticale de lungime 1, între originea sistemului de axe și punctul de coordonate (N, N), cu lungimea totală 2∙N.

Cerința
Să se determine numărul total de căi distincte. De exemplu, dacă N = 3 și dintre toate liniile desenate se șterg K = 4 linii (liniile subțiri), atunci conform figurilor de mai jos, numărul total de căi distincte va fi 6.



Date de intrare
Fișierul de intrare npath.in conține pe prima linie numerele N și K, despărțite printr-un spațiu, cu semnificaţia de mai sus, iar pe fiecare din următoarele K linii va fi câte un triplet de numere x, y, d având următoarea semnificație:


x, y reprezintă coordonatele punctului de unde începe să se șteargă o linie.
d = 1 dacă linia va fi ștearsă pe orizontală către dreapta.
d = 2 dacă linia va fi ștearsă pe verticală în sus.

Date de ieșire
Fișierul de ieșire npath.out va conține pe prima linie restul împărțirii numărului total de căi distincte la 3000017.

Restricții și precizări

1 ≤ N ≤ 5000
0 ≤ K ≤ 100
două căi sunt distincte dacă succesiunea de linii orizontale și verticale diferă prin cel puțin o poziție
pentru teste în valoare de 52 puncte 0 ≤ K ≤ 15

Exemplu:
npath.in

3 4
1 0 2
2 1 2
2 2 1
1 2 2
npath.out

6
Explicație
N = 3 și K = 4. Din grila inițială se șterg 4 linii și anume:


Linia verticală dintre punctele de coordonate (1,0) și (1,1)
Linia verticală dintre punctele de coordonate (2,1) și (2,2)
Linia orizontală dintre punctele de coordonate (2,2) și (3,2)
Linia verticală dintre punctele de coordonate (1,2) și (1,3)

-În total sunt 6 moduri diferite de a ajunge din origine în punctul de coordonate (3,3) fără a trece prin liniile șterse (conform figurilor de mai sus). Restul împărțirii lui 6 la 3000017 este 6.

## Cod sursă C++

```cpp
// prof. Chesca Ciprian
// sursa cu recurenta pe matrice ~ 100 p
// O(N^2)
#include <fstream>
#define nmax 5001
#define M 3000017
using namespace std;
int m[nmax][nmax],a[nmax][nmax];
int x[nmax],y[nmax];
ifstream fin("npath.in");
ofstream fout("npath.out");
int main()
{
    int i,j,n,k,d,x0,y0;
    fin >> n >> k;
    // 1  = lipsa unei linii orizontale si 2 = lipsa unei linii verticale din pozitia (x0,y0)
    for(i=1;i<=k;i++)
        {
        fin >> x0 >> y0 >> d;
        if (d == 1) a[x0][y0]+=d;
        if (d == 2) a[x0][y0]+=d;
        }
    // adaug restrictiile
    // calculez vectorii x si y ce reprezinta valorile lui m de pe prima linie respectiv prima coloana
    if (a[0][0]==1 || a[0][0]==3) x[0] = 0;
                                 else x[0] = 1;
    for(i=1;i<=n;i++)
        if (a[0][i] == 1 || a[0][i] == 3) x[i] = 0;
            else  x[i] = x[i-1] && 1;
    if (a[0][0] == 2 || a[0][0] == 3) y[0] = 0;
        else y[0] = 1;
    for(j=1;j<=n;j++)
        if (a[j][0] == 2 || a[j][0] == 3 ) y[j] = 0;
          else y[j] = y[j-1] && 1;
    // calculez elementul din coltul (0,0) al matricei m
    if (a[0][0]==3) m[0][0]=0;
              else
                {
                if (a[0][0]==2 && (a[0][1]==1 || a[0][1] == 0)) m[0][0]=1;
                if (a[0][0]==1 && (a[1][0]==2 || a[1][0] == 0)) m[0][0]=1;
                if (a[0][0]==0 && (a[1][0])==0 || a[1][0] == 2) m[0][0]++;
                if (a[0][0]==0 && (a[0][1])==0 || a[0][1] == 1) m[0][0]++;
                }
    // calculez recurent prima linie din matricea m
    for(i=1;i<=n;i++)
        {
        if (a[0][i+1] == 0 || a[0][i+1] == 1) m[0][i]=(m[0][i]+x[i])%M;
        if (a[1][i] == 0 || a[1][i] == 2) m[0][i]=(m[0][i]+m[0][i-1])%M;
        }
    // calculez recurent prima coloana din matricea m
    for(i=1;i<=n;i++)
        {
        if (a[i+1][0] == 0 || a[i+1][0] == 2) m[i][0]=(m[i][0]+y[i])%M;
        if (a[i][1] == 0 || a[i][1] == 1) m[i][0]=(m[i][0]+m[i-1][0])%M;
        }
    // calculez recurent restul elementelor din matrice
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
              {
               if (a[i][j+1] == 0 || a[i][j+1] == 1) m[i][j]=(m[i][j]+m[i-1][j])%M;
               if (a[i+1][j] == 0 || a[i+1][j] == 2) m[i][j]=(m[i][j]+m[i][j-1])%M;
              }
    fout << m[n-1][n-1]<<"\n";
	fout.close();
    return 0;
}
```

## Resurse

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