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 anumite camere se află echipe de pompieri. Pentru o intervenție cât ma...

2023-12-07T18:11:19Z

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 anumite camere se află echipe de pompieri. Pentru o intervenție cât ma...

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 anumite camere se află echipe de pompieri. Pentru o intervenție cât mai rapidă în cazul unui eventual incendiu apărut în una dintre camerele clădirii, este necesar să se știe, pentru fiecare cameră care este timpul minim în care o echipă de pompieri ajunge în acea cameră.

==Date de intrare==

Fișierul de intrare '''acces1in.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ă o cameră în care se găsește o echipă de pompieri

==Date de ieșire==

Fișierul de ieșire '''acces1out.txt''' va conține o matrice cu '''n''' linii și '''m''' coloane, fiecare element al matricei reprezentând timpul minim necesar ca o echipă de pompieri să ajungă în camera corespunzătoare. Pentru camerele ocupate se va fișa simbolul '''#''', iar pentru cele libere în care nu va ajunge nici o echipă se va afișa '''-'''.
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:==

'''acces1in.txt'''

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

'''acces1out.txt'''

Datele de intrare corespund restrictiilor impuse
0 1 # - # 0
1 2 # # 2 1
2 1 0 1 2 2
3 2 1 2 3 #

==Exemplul 2:==

'''acces1in.txt'''

acces1

'''acces1out.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):
if n_linii > 1000 or m_coloane > 1000:
raise ValueError
for linie in matrice:
for caracter in linie:
if caracter not in ['-', '#', 'P']:
raise ValueError

def bfs(n_linii, m_coloane, matrice):
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
distanta = [[-1] * m_coloane for _ in range(n_linii)]
q = deque()

for nr_i in range(n_linii):
for nr_j in range(m_coloane):
if matrice[nr_i][nr_j] == 'P':
q.append((nr_i, nr_j))
distanta[nr_i][nr_j] = 0

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

return distanta

if __name__ == '__main__':
file_in = open("acces1in.txt", "r")
file_out = open("acces1out.txt", "w")

try:
n, m = map(int, file_in.readline().split())
mat = [list(file_in.readline().strip()) for _ in range(n)]

validare(n, m, mat)
file_out.write("Datele de intrare corespund restrictiilor impuse\n")
dist = bfs(n, m, mat)

for i in range(n):
for j in range(m):
if mat[i][j] == '#':
file_out.write('# ')
elif dist[i][j] == -1:
file_out.write('- ')
else:
file_out.write(str(dist[i][j]) + ' ')
file_out.write('\n')

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

</syntaxhighlight>

0868 - Acces1 - Revision history