Catalin Moje at 20:41, 14 May 2023

2023-05-14T20:41:29Z

← Older revision		Revision as of 20:41, 14 May 2023
Line 20:		Line 20:
	==Restricții și precizări==		==Restricții și precizări==

	1 ≤ n , m ≤ 100		*1 ≤ n , m ≤ 100

	==Exemplu ==		==Exemplu ==

			:Intrare
	~~fill~~.in		;moscraciun.in
	~~<syntaxhighlight lang="python">~~		;4 6
	4 6		;1 1 1 0 1 0
	1 1 1 0 1 0		;0 0 1 0 1 1
	0 0 1 0 1 1		;1 1 1 0 0 0
	1 1 1 0 0 0		;0 1 0 1 1 1
	0 1 0 1 1 1
	~~</syntaxhighlight>~~		:Iesire:
			;moscraciun.out
			;3

	~~fill.out~~
	~~<syntaxhighlight lang="python">~~
	3
	~~</syntaxhighlight>~~



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

	import sys		import sys
Line 97:		Line 95:

	==Explicații ==		==Explicații ==
	Funcția validare primește ca argumente matricea de intrare și dimensiunile acesteia (n și m). Aceasta verifică dacă toate elementele matricei sunt 0, 1, 2 sau 3, returnând False dacă nu este cazul și True altfel.		#1 Funcția validare primește ca argumente matricea de intrare și dimensiunile acesteia (n și m). Aceasta verifică dacă toate elementele matricei sunt 0, 1, 2 sau 3, returnând False dacă nu este cazul și True altfel.

	Funcția rezolvare primește matricea de intrare și dimensiunile acesteia (n și m). Se caută poziția lui Moș Crăciun în matrice (elementul cu valoarea 2) și se adaugă în coada q ca punct de plecare pentru parcurgerea grafului. În timpul parcurgerii BFS, se verifică dacă fiecare nod adiacent este de tip 1 sau 3, adică dacă se poate ajunge la el și se mai pot colecta spiriduși. Nodurile deja vizitate sunt stocate în setul vizitat. La final, funcția returnează numărul de spiriduși colectați.		#2 Funcția rezolvare primește matricea de intrare și dimensiunile acesteia (n și m). Se caută poziția lui Moș Crăciun în matrice (elementul cu valoarea 2) și se adaugă în coada q ca punct de plecare pentru parcurgerea grafului. În timpul parcurgerii BFS, se verifică dacă fiecare nod adiacent este de tip 1 sau 3, adică dacă se poate ajunge la el și se mai pot colecta spiriduși. Nodurile deja vizitate sunt stocate în setul vizitat. La final, funcția returnează numărul de spiriduși colectați.

	Funcția main citește matricea de intrare din fișierul "moscraciun.in", verifică validitatea acesteia prin apelul funcției validare, și afișează un mesaj de eroare dacă matricea este invalidă. Altfel, rezultatul returnat de funcția rezolvare este scris în fișierul "moscraciun.out" prin intermediul modulului sys.		#3 Funcția main citește matricea de intrare din fișierul "moscraciun.in", verifică validitatea acesteia prin apelul funcției validare, și afișează un mesaj de eroare dacă matricea este invalidă. Altfel, rezultatul returnat de funcția rezolvare este scris în fișierul "moscraciun.out" prin intermediul modulului sys.

Catalin Moje: Pagină nouă: ==Cerința== Moș Crăciun locuiește la polul nord și pregătește cadouri pentru copii cuminți din clasele a X-a B și A, ajutat de mai mulți spiriduși. Datorită încălzirii globale, gheața se topește, formându-se mai multe banchize. Spiridușii care se află pe alte banchize decât Moș Crăciun nu-l mai pot ajuta pe acesta, spre disperarea generală. Harta polului nord seamănă cu o matrice cu n linii și m coloane în care elementele pot avea următoarele val...

2023-04-29T17:44:14Z

Pagină nouă: ==Cerința== Moș Crăciun locuiește la polul nord și pregătește cadouri pentru copii cuminți din clasele a X-a B și A, ajutat de mai mulți spiriduși. Datorită încălzirii globale, gheața se topește, formându-se mai multe banchize. Spiridușii care se află pe alte banchize decât Moș Crăciun nu-l mai pot ajuta pe acesta, spre disperarea generală. Harta polului nord seamănă cu o matrice cu n linii și m coloane în care elementele pot avea următoarele val...

New page

==Cerința==
Moș Crăciun locuiește la polul nord și pregătește cadouri pentru copii cuminți din clasele a X-a B și A, ajutat de mai mulți spiriduși. Datorită încălzirii globale, gheața se topește, formându-se mai multe banchize. Spiridușii care se află pe alte banchize decât Moș Crăciun nu-l mai pot ajuta pe acesta, spre disperarea generală.

Harta polului nord seamănă cu o matrice cu n linii și m coloane în care elementele pot avea următoarele valori:

0 – zonă cu apă, în care gheața s-a topit.
1 – zonă cu gheață care face parte dintr-o banchiză. Două zone cu gheață fac parte din aceeași banchiză dacă se învecinează pe linie sau pe coloană.
2 – zonă cu gheață în care se găsește Moș Crăciun.
3 – zonă cu gheață în care se găsește un spiriduș
Scrieți un program care să determine câți spiriduși se află pe aceeași banchiză cu Moș Crăciun și îl pot ajuta în continuare să pregătească cadouri pentru copii cuminți din clasele a X-a B și A.

==Date de intrare==

Fișierul de intrare moscraciun.in conține pe prima linie numerele n m. Următoarele n linii conțin câte m elemente, 0, 1, 2 sau 3, cu semnificația din enunț.

==Date de ieșire==
Fișierul de ieșire moscraciun.out va conține pe prima linie numărul C spiriduși de pe banchiza lui Moș Crăciun.

==Restricții și precizări==

1 ≤ n , m ≤ 100

==Exemplu ==

fill.in
<syntaxhighlight lang="python">
4 6
1 1 1 0 1 0
0 0 1 0 1 1
1 1 1 0 0 0
0 1 0 1 1 1
</syntaxhighlight>

fill.out
<syntaxhighlight lang="python">
3
</syntaxhighlight>

==Rezolvare==
<syntaxhighlight lang="python">

import sys

def validare(matrice, n, m):
"""
Verifică dacă matricea de intrare este validă.
"""
for i in range(n):
for j in range(m):
if matrice[i][j] not in [0, 1, 2, 3]:
return False
return True

def rezolvare(matrice, n, m):
"""
Determină numărul de spiriduși de pe aceeași banchiză cu Moș Crăciun.
"""
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
q = [(i, j) for i in range(n) for j in range(m) if matrice[i][j] == 2] # coordonatele lui Mos Craciun
vizitat = set(q) # nodurile vizitate
count = 0 # numarul de spiridusi gasiti
while q:
x, y = q.pop(0)
if matrice[x][y] == 3:
count += 1
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m and matrice[nx][ny] in [1, 3] and (nx, ny) not in vizitat:
vizitat.add((nx, ny))
q.append((nx, ny))
return count

def main():
with open("moscraciun.in", "r") as f:
n, m = map(int, f.readline().split())
matrice = [[int(x) for x in f.readline().split()] for i in range(n)]
if not validare(matrice, n, m):
print("Matricea de intrare nu este valida.", file=sys.stderr)
sys.exit(1)
with open("moscraciun.out", "w") as f:
f.write(str(rezolvare(matrice, n, m)))

if __name__ == "__main__":
main()

</syntaxhighlight>

==Explicații ==
Funcția validare primește ca argumente matricea de intrare și dimensiunile acesteia (n și m). Aceasta verifică dacă toate elementele matricei sunt 0, 1, 2 sau 3, returnând False dacă nu este cazul și True altfel.

Funcția rezolvare primește matricea de intrare și dimensiunile acesteia (n și m). Se caută poziția lui Moș Crăciun în matrice (elementul cu valoarea 2) și se adaugă în coada q ca punct de plecare pentru parcurgerea grafului. În timpul parcurgerii BFS, se verifică dacă fiecare nod adiacent este de tip 1 sau 3, adică dacă se poate ajunge la el și se mai pot colecta spiriduși. Nodurile deja vizitate sunt stocate în setul vizitat. La final, funcția returnează numărul de spiriduși colectați.

Funcția main citește matricea de intrare din fișierul "moscraciun.in", verifică validitatea acesteia prin apelul funcției validare, și afișează un mesaj de eroare dacă matricea este invalidă. Altfel, rezultatul returnat de funcția rezolvare este scris în fișierul "moscraciun.out" prin intermediul modulului sys.

1864 - MosCraciun - Revision history

Catalin Moje at 20:41, 14 May 2023