Question

Într-o zi telefonul lui Max s-a stricat.Văzând o reclamă la noul telefon cu sistemul de operare Ubuntu, s-a gândit să achiziționeze și el unul.

Drumul de la casa lui la magazin poate fi reprezentat ca o matrice cu n linii și m coloane. În fiecare element al matricei este o barieră; pentru a trece de bariere trebuie plătită o sumă de bani, care nu este aceeași pentru fiecare barieră și poate fi chiar 0.

Casa lui se află pe coordonatele (ic,jc), iar magazinul la coordonatele (im,jm).
Pentru că trebuie să cumpere telefonul, este nevoie ca drumul lui sa fie cât mai puțin costisitor, plătind la bariere o sumă totală minimă.

Date de intrare
Fișierul de intrare ubuph.in conține pe prima linie numerele n si m, iar pe următoarele n linii, câte m numere naturale reprezentând sumele care trebuie plătite la bariere.

Ultima linie va conține coordonatele (im,jm) si (ic,jc) cu proprietatea din enunț.

Date de ieșire
Fișierul de ieșire ubuph.out va conține pe prima linie numărul S, reprezentând suma minimă care trebuie cheltuită pentru a ajunge la magazin.

Restricții și precizări
1 ≤ n,m ≤ 1000.
elementele matricei vor fi mai mici decât 1.000.000.
dacă Max se poate deplasa numai pe linii sau pe coloane și nu poate ieși din matrice.
Exemplu
ubuph.in

4 4
1 0 0 5
6 1 2 8
10 10 10 1
1 10 0 1
1 1 3 3
ubuph.out

13

Answer 1

#include <fstream>
#include <queue>
#define INF 1000000000
using namespace std;

int A[1001][1001],B[1001][1001],n,m,im,jm,ic,jc;
const int di[]={1,-1,0,0},dj[]={0,0,1,-1};// Deplasarea spre magazin
queue<pair<int,int> >Q;// Initializarea cozii

void citire()
{
    ifstream  f("ubuph.in");
    f>>n>>m;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            f>>A[i][j];
            B[i][j]=INF;
        }
    f>>im>>jm>>ic>>jc;
    f.close();
}

bool verif(int i,int j)// Verifica daca pozitia curenta se afla in matrice
{
    return 1<=i&&i<=n&&1<=j&&j<=m;
}

void Lee()
{   B[ic][jc]=A[ic][jc];
    while(!Q.empty())
    {
        pair<int,int> P=Q.front();
        for(int k=0;k<4;++k)
        {
            int i=P.first+di[k],j=P.second+dj[k];
            if(verif(i,j)&&B[i][j]>B[P.first][P.second]+A[i][j])
                B[i][j]=B[P.first][P.second]+A[i][j],Q.push(make_pair(i,j));
        }
        Q.pop();
    }
}

int main()
{
    citire();
    Q.push(make_pair(ic,jc));
    Lee();
    ofstream g("ubuph.out");
    g<<B[im][jm];
    g.close();
    return 0;
}