1238 - Labirint

Cerința

Zoli și D’Umbră s-au pierdut într-un labirint cu n x n camere dispuse pe cate n linii și n coloane. D’umbră se află în camera (1, 1), iar Zoli se află în camera (n, n). Aceștia vor trebui să parcurgă labirintul pentru a se regăsi. Dacă unul dintre ei se aflâ în camera (i, j), acesta se poate deplasa spre una din camerele aflate la pozițiile (i + 1, j), (i, j + 1), (i - 1, j) sau (i, j - 1), 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ță R care poate fi spartă cu un baros cu o putere P ≥ R. Unul dintre cei doi (nu contează care) va avea acces la un arsenal de barosuri cu puteri între 0 și 100.000.

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 labirint.in conține pe prima linie numărul n, iar pe următoarele n linii n numere, al j -lea număr de pe linia i + 1 reprezintă rezistența ușii de la camera aflată în (i, j).

Date de ieșire

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

Restricții și precizări

• 1 ≤ n ≤ 1.000
• 0 ≤ rezistența unei uși ≤ 100.000
• pentru 50% din punctaj, Pmin ≤ 600 și n ≤ 500

Exemplu:

labirint.in

4
1 2 3 4 
2 3 1 4 
2 1 2 3
3 3 1 1 

labirint.out

2

Explicație

(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (4, 3) -> (4, 4)

Se evită camerele cu rezistență mai mare decât 2.

Încărcare soluție

Lipește codul aici

import queue

fin = open("labirint.in", "r")
fout = open("labirint.out", "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()