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>