Raul: Pagină nouă: = 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`. C...

2023-12-21T16:06:21Z

Pagină nouă: = 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 <code>n</code> linii și <code>m</code> 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 <code>0</code>. C...

New page

= 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 <code>n</code> linii și <code>m</code> 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 <code>0</code>. Casa lui Max se află pe coordonatele <code>(ic,jc)</code>, iar magazinul la coordonatele <code>(im,jm)</code>.

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 <code>ubuph.in</code> conține pe prima linie numerele <code>n</code> si <code>m</code>, iar pe următoarele <code>n</code> linii, câte <code>m</code> numere naturale reprezentând sumele care trebuie plătite la bariere.

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

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

= Restricții și precizări =

* <code>1 ≤ n,m ≤ 1000</code>.
* elementele matricei vor fi mai mici decât <code>1.000.000</code>.
* Max se poate deplasa numai pe linii sau pe coloane și nu poate ieși din matrice.

= Exemplu: =
<code>ubuph.in</code>
4 4
1 0 0 5
6 1 2 8
10 10 10 1
1 10 0 1
1 1 3 3
<code>ubuph.out</code>
13

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import queue

INF = 1000000000
n = 0
m = 0
im = 0
jm = 0
ic = 0
jc = 0
di = [1, -1, 0, 0]
dj = [0, 0, 1, -1]
Q = queue.Queue()

def Inside(i, j):
return 1 <= i and i <= n and 1 <= j and j <= m

def citire():
global n, m, im, jm, ic, jc
with open("ubuph.in", "r") as fin:
n, m = map(int, fin.readline().split())
for i in range(1, n + 1):
for j in range(1, m + 1):
A[i][j] = int(fin.readline())
B[i][j] = INF
im, jm, ic, jc = map(int, fin.readline().split())

def Lee():
B[ic][jc] = A[ic][jc]
while not Q.empty():
P = Q.get()
for k in range(4):
i = P[0] + di[k]
j = P[1] + dj[k]
if Inside(i, j) and B[i][j] > B[P[0]][P[1]] + A[i][j]:
B[i][j] = B[P[0]][P[1]] + A[i][j]
Q.put((i, j))
Q.get()

citire()
Q.put((ic, jc))
Lee()
with open("ubuph.out", "w") as fout:
fout.write(str(B[im][jm]))

</syntaxhighlight>

1871 - UbuPH - Revision history