Editing 1238 - Labirint


= Cerința =
Zoli și D’Umbră s-au pierdut într-un labirint cu <code>n x n</code> camere dispuse pe cate <code>n</code> linii și <code>n</code> coloane. D’umbră se află în camera <code>(1, 1)</code>, iar Zoli se află în camera <code>(n, n)</code>. Aceștia vor trebui să parcurgă labirintul pentru a se regăsi. Dacă unul dintre ei se aflâ în camera <code>(i, j)</code>, acesta se poate deplasa spre una din camerele aflate la pozițiile <code>(i + 1, j)</code>, <code>(i, j + 1)</code>, <code>(i - 1, j)</code> sau <code>(i, j - 1)</code>, fără a părăsi labirintul.

Camerele nu pot fi accesate ușor. La fiecare cameră se află câte o ușă având o rezistență <code>R</code> care poate fi spartă cu un baros cu o putere <code>P ≥ R</code>. Unul dintre cei doi (nu contează care) va avea acces la un arsenal de barosuri cu puteri între <code>0</code> și <code>100.000</code>.

Determinați puterea minimă pe care o poate avea barosul ce trebuie folosit astfel încât Zoli și D’Umbră să se poată întâlni.

= Date de intrare =
Fișierul de intrare <code>labirint.in</code> conține pe prima linie numărul <code>n</code>, iar pe următoarele <code>n</code> linii <code>n</code> numere, al <code>j</code> -lea număr de pe linia <code>i + 1</code> reprezintă rezistența ușii de la camera aflată în <code>(i, j)</code>.

= Date de ieșire =
Fișierul de ieșire <code>labirint.out</code> va conține pe prima linie numărul <code>Pmin</code>, reprezentând puterea minimă pe care o poate avea un baros folosit pentru a sparge anumite uși și a conecta camerele <code>(1, 1)</code> și <code>(n, n)</code>.

= Restricții și precizări =

* <code>1 ≤ n ≤ 1.000</code>
* <code>0 ≤</code> rezistența unei uși <code>≤ 100.000</code>
* pentru <code>50%</code> din punctaj, <code>Pmin ≤ 600</code> și <code>n ≤ 500</code>

= Exemplu: =
<code>labirint.in</code>
 4
 1 2 3 4 
 2 3 1 4 
 2 1 2 3
 3 3 1 1 
<code>labirint.out</code>
 2

=== Explicație ===
<code>(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (4, 3) -> (4, 4)</code>

Se evită camerele cu rezistență mai mare decât <code>2</code>.

== Încărcare soluție ==

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

fin = open("labirint.txtin", "r")
fout = open("labirint.txtout", "w")
N = 1005
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
a = [[0] * N for _ in range(N)]
v = [[0] * N for _ in range(N)]
n = 0
sol = 0
step = 1 << 16
Q = queue.Queue()

def lee(k):
    global Q
    global v
    global n
    global a
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            v[i][j] = 0
    if a[1][1] <= k:
        Q.put((1, 1))
    else:
        return 0
    while not Q.empty() and not v[n][n]:
        x, y = Q.get()
        for crt in range(4):
            xx = x + dx[crt]
            yy = y + dy[crt]
            if not v[xx][yy] and a[xx][yy] <= k:
                v[xx][yy] = 1
                Q.put((xx, yy))
    while not Q.empty():
        Q.get()
    return v[n][n]

n = int(fin.readline())
for i in range(1, n + 1):
    a[i] = list(map(int, fin.readline().split()))
for i in range(n + 2):
    for j in range(n + 2):
        v[i][j] = 1
while step:
    if not lee(sol + step):
        sol += step
    step >>= 1
fout.write(str(sol + 1))
fin.close()
fout.close()


</syntaxhighlight>