# PBinfo #4379 – moara – Rezolvare C++

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

## Enunț

Cunoscutul “afacerist” din nuvela “Moara cu noroc”, Lică Sămădăul, a fost demascat pentru nenumăratele furturi pe care acesta le-a săvârșit. Din frică pentru ce urmează să apară, acesta s-a decis să fugă cât mai repede din sat. Satul poate fi reprezentat sub forma a N*M celule, organizate pe N linii (numerotate de la 1 la N) și M coloane (numerotate de la 1 la M). Fiecare celulă ca fi identificată prin coordonatele sale (i,j) (linia, respectiv coloana pe care se află celula). Casa lui Lică este în celula de coordonate (1,1), iar ieșirea din sat este în celula de coordonate (N, M). 

Lică își ia toate obiectele de valoare din casă și se hotărăște să părăsească satul pe un cal. El are în grajd C cai frumoși. Fiecare cal i (1 ≤ i ≤ C) are o forță inițială f[i]. Orice cal se poate deplasa la un pas doar în una dintre celule învecinate (pe linie sau pe coloană). Fiecare celulă (i,j) (1 ≤ i ≤ N, 1 ≤ j ≤ M) are asociate două valori cu următoarea semnificație:


a[i][j] – pentru ca Lică să poată intra în celula de coordonate (i,j), calul său trebuie să aibă în acel moment o forţă mai mare sau egală cu a[i][j];
p[i][j] – în momentul ieşirii din celula de coordonate (i,j), calul lui Lică va pierde p[i][j] din forța sa.

Aceste valori vor fi reținute în două matrici, notate a, respectiv p.

Cerința
Cunoscându-se N și M, dimensiunile satului, C numărul cailor, forțele inițiale ale cailor și matricile a și p, să se determine numărul de cai pe care Lică îi poate utiliza astfel încât el să reușească să traverseze satul, de la casa lui până la ieșirea din sat.

Date de intrare
Fișierul de intrare moara.in conține pe prima linie numerele naturale N, M și C. Pe a doua linie se află C numere naturale reprezentând forțele inițiale ale cailor. Pe următoarele N linii se află câte M numere naturale, reprezentând elementele matricei a. Pe următoarele N linii se află câte M numere, reprezentând elementele matricei p. Valorile scrise pe aceeași linie vor fi separate prin câte un spațiu.

Date de ieșire
Fișierul de ieșire moara.out va conține o singură linie pe care va fi scris numărul cailor care au suficientă forță pentru a traversa satul, de la casa lui Lică până la ieșirea din sat.

Restricții și precizări

1 ≤ N, M ≤ 700
1 ≤ C ≤ 1.000.000
Elementele matricelor a și p sunt numere naturale nenule ≤ 100.000
Forțele cailor sunt numere naturale nenule ≤ 1.000.000.000

Exemplu:
moara.in

3 3 4
91 2 3 54
3 2 1
1 2 3
2 2 2
1 1 1
2 2 1
1 2 1
moara.out

2
Explicație
Lică poate traversa satul, respectând restricțiile impuse de enunț, doar pe primul și ultimul cal.

## Cod sursă C++

```cpp
/*
    Autor: Raileanu Alin-Gabriel
*/
#include <fstream>
#include <queue>
#include <algorithm>
const int NMAX=1005;
using namespace std;
ifstream fin("moara.in");
ofstream fout("moara.out");
struct moment
{
    int lin, col;
};
queue <moment> s;
bool viz[NMAX][NMAX];
long long n, m, k, maxim, nrc;
long long d[NMAX][NMAX], f[NMAX*NMAX];
long long c[NMAX][NMAX], a[NMAX][NMAX];
int dl[]= {0, 0, -1, 1};
int dc[]= {-1, 1, 0, 0};
bool traverseaza(long long);
long long cautare_binara();
void bordare();
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    int i, j;
    int minim, ans=0;
    fin>>n>>m>>nrc;
    bordare();
    for(i=1; i<=nrc; i++)
    {
        fin>>f[i];
    }
    sort(f+1, f+nrc+1);
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            fin>>a[i][j];
        }
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            fin>>c[i][j];
        }
    }
    minim=cautare_binara();
    fout<<nrc-minim+1<<'\n';
    return 0;
}
void bordare()
{
    int i;
    for(i=0; i<=n+1; i++) a[i][0]=a[i][m+1]=1e18;
    for(i=0; i<=m+1; i++) a[0][i]=a[n+1][i]=1e18;
}
long long cautare_binara()
{
    long long st=1, dr=nrc, mij, gasit=nrc+1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(traverseaza(f[mij]))
        {
            dr=mij-1;
            gasit=mij;
        }
        else st=mij+1;
    }
    return gasit;
}
bool traverseaza(long long fortza)
{
    int i, j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            d[i][j]=-1;
        }
    }
    if(fortza<a[1][1]) return false;
    moment p;
    while(!s.empty()) s.pop();
    s.push({1, 1});
    d[1][1]=fortza;
    while(!s.empty())
    {
        p=s.front();
        if(p.lin==n && p.col==m) return true;
        for(i=0; i<4; i++)
        {
            if(d[p.lin+dl[i]][p.col+dc[i]]<(d[p.lin][p.col]-c[p.lin][p.col]) && (d[p.lin][p.col]-c[p.lin][p.col])>=a[p.lin+dl[i]][p.col+dc[i]])
            {
                d[p.lin+dl[i]][p.col+dc[i]]=(d[p.lin][p.col]-c[p.lin][p.col]);
                s.push({p.lin+dl[i], p.col+dc[i]});
            }
        }
        s.pop();
    }
    return false;
}
```

## Resurse

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