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.