2251 - Pereti

Enunț

Localitatea Târgovişte este în plină modernizare. Primăria decide să inventarieze toate clădirile din oraş pentru a renova faţadele acestora. În acest sens analizează harta oraşului şi constată că toţi pereţii sunt aşezaţi doar pe direcţia Nord Sud sau Est Vest. Pereţii vizibili de către turiști sunt doar aceia la care se poate ajunge din exteriorul orașului prin deplasarea pe cele două direcţii date, în oricare din cele patru sensuri (N, E, S, V). Harta oraşului este întocmită pe un caroiaj format din pătrate cu latura 1.

Cerința

Cunoscându-se harta oraşului, determinaţi lungimea pereţilor vizibili ce urmează a fi zugrăviţi.

Date de intrare

Fișierul de intrare pereti.in are pe prima linie dimensiunile m (numărul de linii), n (numărul de coloane) ale hărţii. Pe fiecare dintre următoarele m linii există n numere naturale de la 0 la 15, separate prin câte un spaţiu, cu semnificaţia: reprezentarea binară a numărului pe 4 cifre semnifică, începând de la stânga spre dreapta, existenţa unui perete spre direcţiile N, E, S, V. (1- există perete, 0 – nu există perete, explicaţii în figura de mai jos). De exemplu valoarea 13 se reprezintă în binar 1101, deci în mod corespunzător, de la stânga spre dreapta, vom avea pereţi spre N, E şi V.

Date de ieșire

Fișierul de ieșire pereti.out va conţine pe prima linie numărul natural k reprezentând lungimea pereților ce vor fi zugrăviți.

Restricții și precizări

• 1 ≤ m, n ≤ 100
• Pereţii aflaţi la marginea hărţii sunt pereţi vizibili.
• Datele de intrare sunt considerate corecte.

Exemplu

Exemplu1

Intrare:

pereti.in

5 4

0 6 13 1

4 15 5 1

0 14 7 1

4 15 9 0

0 12 5 7

Iesire:

pereti.out

22

Rezolvare

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

from collections import deque

def validate_input(m, n, harta):

   if not (1 <= m <= 100 and 1 <= n <= 100):
       return False
   for linie in harta:
       for valoare in linie:
           if not (0 <= valoare <= 15):
               return False
   return True

def rezolvare(m, n, harta):

   # lista cu directiile in care se poate merge
   directii = [(0, 1), (1, 0), (0, -1), (-1, 0)]
   # codurile pentru peretii dintre directiile din lista
   coduri = [1, 2, 4, 8]

   pereti = 0
   for i in range(m):
       for j in range(n):
           for idx, d in enumerate(directii):
               # verifica daca pozitia vecina este valida
               if i + d[0] >= 0 and i + d[0] < m and j + d[1] >= 0 and j + d[1] < n:
                   # verifica daca peretele face parte din perimetrul exterior
                   if i == 0 and idx == 3 or i == m - 1 and idx == 1 or j == 0 and idx == 2 or j == n - 1 and idx == 0:
                       continue
                   # calculeaza codul peretelui dintre cele doua pozitii
                   p1 = harta[i][j]
                   p2 = harta[i + d[0]][j + d[1]]
                   cod = coduri[idx]
                   if p1 & cod == 0 and p2 & coduri[(idx + 2) % 4] == 0:
                       # daca cele doua pereti sunt nevopsiti, ii vopsim
                       pereti += 2
                       harta[i][j] += cod
                       harta[i + d[0]][j + d[1]] += coduri[(idx + 2) % 4]

   # Afisare harta si variabile de debug
   for linie in harta:
       print(linie)
   print(pereti)

   # returneaza numarul de pereti vopsiti
   return pereti

def main():

   with open("pereti.in") as f:
       m, n = map(int, f.readline().split())
       harta = []
       for i in range(m):
           harta.append(list(map(int, f.readline().split())))
   lungime = rezolvare(m, n, harta)
   with open("pereti.out", "w") as f:
       f.write(str(lungime) + '\n')

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicații

Funcția rezolvare primește dimensiunile labirintului m și n și o matrice harta reprezentând labirintul cu m linii și n coloane. Scopul funcției este de a determina numărul total de pereți ce trebuie vopsiți astfel încât să se poată ieși din labirint.

În primul rând, se definesc toate direcțiile posibile în care se poate mișca în labirint, reprezentate sub forma unei liste de tupluri de forma (dx, dy) cu dx și dy reprezentând deplasarea pe axa OX, respectiv OY.

În continuare, se parcurge fiecare celulă din labirint și se verifică dacă există un perete nevopsit între aceasta și fiecare celulă vecină. Pentru fiecare astfel de perete, se calculează codul acestuia și se verifică dacă peretele corespunzător din celula vecină este și el nevopsit. Dacă aceste condiții sunt îndeplinite, atunci cele două perete sunt vopsite și numărul total de pereti vopsiți este incrementat cu 2.

În final, se afișează matricea harta și numărul total de pereti vopsiți, iar apoi acesta este returnat.

În funcția main, se deschide fișierul de intrare pereti.in și se citesc dimensiunile labirintului și matricea harta. Se apelează funcția rezolvare și se obține numărul de pereti vopsiți, care este apoi scris în fișierul de ieșire pereti.out.