Raul: /* Lipește codul aici */

2023-12-21T16:09:34Z

Lipește codul aici

← Older revision		Revision as of 16:09, 21 December 2023
Line 40:		Line 40:
	import queue		import queue

	fin = open("labirint.~~txtin~~", "r")		fin = open("labirint.in", "r")
	fout = open("labirint.~~txtout~~", "w")		fout = open("labirint.out", "w")
	N = 1005		N = 1005
	dx = [-1, 0, 1, 0]		dx = [-1, 0, 1, 0]

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

2023-12-21T16:09:10Z

Pagină nouă: = 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>,...

New page

= 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>

1238 - Labirint - Revision history

Raul: /* Lipește codul aici */