Cerința

Î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 Max 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.
Max se poate deplasa numai pe linii sau pe coloane și nu poate ieși din matrice.

Exemplu

ubuph.in

ubuph.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 UbuPH:

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

ifstream  fin("ubuph.in");
ofstream fout("ubuph.out");

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};//deviatiile
queue<pair<int, int> > Q;// initializare coada

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

void citire()
{fin >> n >> m;
        for(int i =1 ; i <= n ; i ++)
        for(int j = 1 ; j <= m ; j ++)
            {fin >> A[i][j];
             B[i][j] = INF;
           }  
    fin >> im >> jm >> ic >> jc;
}

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( Inside(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();
    fout << B[im][jm];
    fin.close(), fout.close();//ichiderea fisierelor
    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 #1871 UbuPH

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1871 UbuPH 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 #1871 UbuPH