Editing 0866 - Acces

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