Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Se consideră o clădire de formă dreptunghiulară, împărțită în '''n*m''' camere, dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. Dintr-o cameră se poate trece în oricare dintre cele '''4''' camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut. În una dintre camere se află proprietarul clădirii, care dorește să afle...

2023-12-03T22:11:28Z

Pagină nouă: ==Cerința== Se consideră o clădire de formă dreptunghiulară, împărțită în '''n*m''' camere, dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. Dintr-o cameră se poate trece în oricare dintre cele '''4''' camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut. În una dintre camere se află proprietarul clădirii, care dorește să afle...

New page

==Cerința==

Se consideră o clădire de formă dreptunghiulară, împărțită în '''n*m''' camere, dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane. Dintr-o cameră se poate trece în oricare dintre cele '''4''' camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut.

În una dintre camere se află proprietarul clădirii, care dorește să afle, pentru fiecare dintre camere care este timpul minim necesar pentru a ajunge în acea cameră.

==Date de intrare==

Fișierul de intrare '''accesin.txt''' conține pe prima linie numerele '''n m'''; următoarele '''n''' linii conțin câte '''m''' caractere, care pot fi:

*'''-''' – reprezintă o cameră liberă
*'''#''' – reprezintă o cameră închisă
*'''P''' – reprezintă camera proprietarului, care se consideră liberă

==Date de ieșire==

Fișierul de ieșire '''accesout.txt''' va conține o matrice cu '''n''' linii și '''m''' coloane, elementele matricei reprezentând timpul minim necesar ca proprietarul să ajungă în camere clădirii. Pentru camerele ocupate și pentru camerele libere în care nu se poate ajunge timpul necesar va fi '''-1'''.
Matricea va fi afișată linie cu linie, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin câte un spațiu.

==Restricții și precizări==

*'''1 ≤ n,m ≤ 1000'''

==Exemplul 1:==

'''accesin.txt'''

4 6
--#-#-
--##--
--P---
-----#

'''accesout.txt'''

Datele de intrare corespund restrictiilor impuse
4 3 -1 -1 -1 5
3 2 -1 -1 3 4
2 1 0 1 2 3
3 2 1 2 3 -1

==Exemplul 2:==

'''accesin.txt'''

acces

'''accesout.txt'''

Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque

def validare(n_linii, m_coloane, matrice): # functia de validare a datelor de intrare
if n_linii > 1000 or m_coloane > 1000:
raise ValueError

for linie in matrice:
if len(linie) != m_coloane: # fiecare linie trebuie sa aiba lungimea m
raise ValueError

file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def acces(nr, nc, matrice): # functia de rezolvare
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
dist = [[-1]*nc for _ in range(nr)]
q = deque()

for i in range(nr):
for j in range(nc):
if matrice[i][j] == 'P':
q.append((i, j))
dist[i][j] = 0

while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dx[d], y + dy[d]
if 0 <= nx < nr and 0 <= ny < nc and matrice[nx][ny] != '#' and dist[nx][ny] == -1:
dist[nx][ny] = dist[x][y] + 1
q.append((nx, ny))

for i in range(nr):
for j in range(nc):
file_out.write(str(dist[i][j]) + ' ')
file_out.write('\n')

if __name__ == '__main__':
file_in = open("accesin.txt", "r") # declararea fisierelor
file_out = open("accesout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

# din cauza datelor de intrare pot aparea 2 tipuri de erori, valueError sau IndexError pe care le tratam
try:
n, m = map(int, file_in.readline().split()) # citirea numarului de linii si coloane
mat = [list(file_in.readline().strip()) for _ in range(n)] # citirea matricei

validare(n, m, mat) # apelul functiei de validare
acces(n, m, mat) # apelul functiei de rezolvare

except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

0866 - Acces - Revision history