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

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

#include <bits/stdc++.h>

using namespace std;

ifstream cin("ubuph.in");
ofstream cout("ubuph.out");

int n , m , is , ip , js , jp;
int a[1001][1001];

int inside(int i , int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}

struct poz
{
    int i , j;
};

queue <poz> Q;

const int di[] = { 0 , 0 , -1 , 1};
const int dj[] = {-1 , 1 ,  0 , 0};

long long b[1001][1001];

void lee()
{
    poz r;
    r.i = ip;
    r.j = jp;
    Q.push(r);
    while(!Q.empty())
    {
        poz r;
        r = Q.front();
        for(int i = 0 ; i < 4 ; i++)
        {
            int inou = r.i + di[i];
            int jnou = r.j + dj[i];
            if(inside(inou , jnou) && b[inou][jnou] > a[inou][jnou] + b[r.i][r.j])
            {
                Q.push({inou , jnou});
                b[inou][jnou] = a[inou][jnou] + b[r.i][r.j];
            }
        }
        Q.pop();
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
        cin >> a[i][j];

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            b[i][j] = 20000001;

    cin >> ip >> jp >> is >> js;

    b[ip][jp] = a[ip][jp];
    lee();
    cout << b[is][js];
}