Într-o ţară în care corupţia este în floare şi economia la pământ, pentru a obţine toate aprobările necesare în scopul demarării unei afaceri, investitorul trebuie să treacă prin mai multe camere ale unei clădiri în care se află birouri.

Clădirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pătrat de dimensiune n•n. Pentru a facilita accesul în birouri, toate camerele vecine au uşi între ele. În fiecare birou se află un funcţionar care pretinde o taxă de trecere prin cameră (taxă ce poate fi, pentru unele camere, egală cu 0). Investitorul intră încrezător prin colţul din stânga-sus al clădirii (cum se vede de sus planul clădirii) şi doreşte să ajungă în colţul opus al clădirii, unde este ieşirea, plătind o taxă totală cât mai mică.

Cerința

Ştiind că el are în buzunar S euro şi că fiecare funcţionar îi ia taxa de cum intră în birou, se cere să se determine dacă el poate primi aprobările necesare şi, în caz afirmativ, care este suma maximă de bani care îi rămâne în buzunar la ieşirea din clădire.

Date de intrare

Fişierul de intrare taxe2.in conţine pe prima linie cele două numere S şi n despărţite printr-un spaţiu, iar pe următoarele n linii câte n numere separate prin spaţii ce reprezintă taxele cerute de funcţionarii din fiecare birou.

Date de ieșire

Fişierul de ieşire taxe2.out conţine o singură linie pe care se află numărul maxim de euro care îi rămân în buzunar sau valoarea –1 dacă investitorului nu-i ajung banii pentru a obţine aprobarea.

Restricții și precizări

3 ≤ N ≤ 100
1 ≤ S ≤ 10000
Valorile reprezentând taxele cerute de funcţionarii din birouri sunt numere naturale, o taxă nedepășind valoarea de 200 de euro.

Exemplu

taxe2.in

taxe2.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Taxe2:

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("taxe2.in");
ofstream fout("taxe2.out");
void afis(int m[101][101],int x,int y)
{
    for(int i=1;i<=x;i++)
        {for(int j=1;j<=y;j++)
            cout<<m[i][j]<<" ";
        cout<<"\n";}
}
struct nod
{
    int x,y,c;
    bool operator <(nod x)const
    {
        return c>x.c;
    }
};nod xx;
priority_queue <nod, vector < nod > > q;
int sb,n,a[101][101],co[101][101];
void citire()
{
    fin>>sb>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            fin>>a[i][j];
}
int main()
{
    citire();
    q.push({1,1,a[1][1]});
    while(!q.empty() and co[n][n]==0)
    {
        xx=q.top();
        if(xx.x>1 and co[xx.x-1][xx.y]==0){q.push({xx.x-1,xx.y,xx.c+a[xx.x-1][xx.y]});co[xx.x-1][xx.y]=xx.c+a[xx.x-1][xx.y];}
        if(xx.x<n and co[xx.x+1][xx.y]==0){q.push({xx.x+1,xx.y,xx.c+a[xx.x+1][xx.y]});co[xx.x+1][xx.y]=xx.c+a[xx.x+1][xx.y];}
        if(xx.y>1 and co[xx.x][xx.y-1]==0){q.push({xx.x,xx.y-1,xx.c+a[xx.x][xx.y-1]});co[xx.x][xx.y-1]=xx.c+a[xx.x][xx.y-1];}
        if(xx.y<n and co[xx.x][xx.y+1]==0){q.push({xx.x,xx.y+1,xx.c+a[xx.x][xx.y+1]});co[xx.x][xx.y+1]=xx.c+a[xx.x][xx.y+1];}
        q.pop();
    }
    int val=co[n][n];
    (val>sb)?fout<<-1:fout<<sb-val;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1856 Taxe2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1856 Taxe2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1856 Taxe2