Catalin Moje at 20:38, 14 May 2023

2023-05-14T20:38:27Z

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

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

	==Exemplu ==		==Exemplu ==

			:Intrare:
	fill.in		;fill.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:
			;fill.out

			;3

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



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

	def validare(n, m, harta):		def validare(n, m, harta):
Line 91:		Line 91:
	Pentru a rezolva această problemă, putem folosi o variantă a algoritmului DFS (Depth-First Search) pentru a parcurge matricea. Pentru a număra continentele, vom căuta primul element 1 din matrice și vom căuta toate celulele adiacente cu acestea, marcate cu 1, folosind o căutare în adâncime.		Pentru a rezolva această problemă, putem folosi o variantă a algoritmului DFS (Depth-First Search) pentru a parcurge matricea. Pentru a număra continentele, vom căuta primul element 1 din matrice și vom căuta toate celulele adiacente cu acestea, marcate cu 1, folosind o căutare în adâncime.

	În implementarea noastră, definim o funcție validare_matrice care verifică dacă matricea introdusă în fișierul de intrare este validă, adică are dimensiunile n și m, și are elemente doar 0 sau 1. În caz contrar, programul va afișa un mesaj de eroare.		#1 În implementarea noastră, definim o funcție validare_matrice care verifică dacă matricea introdusă în fișierul de intrare este validă, adică are dimensiunile n și m, și are elemente doar 0 sau 1. În caz contrar, programul va afișa un mesaj de eroare.

	Funcția rezolva primește matricea și dimensiunile acesteia și returnează numărul de continente găsite. Algoritmul DFS este implementat în funcția auxiliară dfs, care primește matricea, poziția curentă și o matrice booleană care urmărește celulele deja vizitate. Algoritmul parcurge matricea în profunzime și marchează celulele vizitate.		#2 Funcția rezolva primește matricea și dimensiunile acesteia și returnează numărul de continente găsite. Algoritmul DFS este implementat în funcția auxiliară dfs, care primește matricea, poziția curentă și o matrice booleană care urmărește celulele deja vizitate. Algoritmul parcurge matricea în profunzime și marchează celulele vizitate.

	În funcția main citim dimensiunile matricei și matricea din fișierul de intrare. Apoi, verificăm dacă matricea este validă. Dacă este validă, apelăm funcția rezolva și afișăm rezultatul în fișierul de ieșire. În caz contrar, afișăm un mesaj de eroare.		#3 În funcția main citim dimensiunile matricei și matricea din fișierul de intrare. Apoi, verificăm dacă matricea este validă. Dacă este validă, apelăm funcția rezolva și afișăm rezultatul în fișierul de ieșire. În caz contrar, afișăm un mesaj de eroare.

	Observăm că, pentru a urmări celulele vizitate în matricea de intrare, folosim o matrice suplimentară visited de dimensiune n x m, care conține valori booleane. Aceasta este utilă pentru a evita parcurgerea acelorași celule de mai multe ori.		Observăm că, pentru a urmări celulele vizitate în matricea de intrare, folosim o matrice suplimentară visited de dimensiune n x m, care conține valori booleane. Aceasta este utilă pentru a evita parcurgerea acelorași celule de mai multe ori.

Catalin Moje: Pagină nouă: ==Cerința== Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unei planete, în care 1 înseamnă uscat, iar 0 înseamnă apă. Două elemente 1 care se învecinează pe linie sau pe coloană (nu și pe diagonală) fac parte din același continent. Să se determine câte continente sunt pe hartă. ==Date de intrare== Fișierul de intrare fill.in conține pe prima linie numerele n m. Următoarele n linii conțin câte m elemente, 0 sau...

2023-04-29T17:15:28Z

Pagină nouă: ==Cerința== Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unei planete, în care 1 înseamnă uscat, iar 0 înseamnă apă. Două elemente 1 care se învecinează pe linie sau pe coloană (nu și pe diagonală) fac parte din același continent. Să se determine câte continente sunt pe hartă. ==Date de intrare== Fișierul de intrare fill.in conține pe prima linie numerele n m. Următoarele n linii conțin câte m elemente, 0 sau...

New page

==Cerința==
Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unei planete, în care 1 înseamnă uscat, iar 0 înseamnă apă. Două elemente 1 care se învecinează pe linie sau pe coloană (nu și pe diagonală) fac parte din același continent.

Să se determine câte continente sunt pe hartă.

==Date de intrare==
Fișierul de intrare fill.in conține pe prima linie numerele n m. Următoarele n linii conțin câte m elemente, 0 sau 1, cu semnificația din enunț.
==Date de ieșire==
Fișierul de ieșire fill.out va conține pe prima linie numărul C de continente existente.

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

def validare(n, m, harta):
if len(harta) != n:
return False
for linie in harta:
if len(linie) != m:
return False
for element in linie:
if element != 0 and element != 1:
return False
return True

def numar_continente(n, m, harta):
visited = [[False for j in range(m)] for i in range(n)]
count = 0
for i in range(n):
for j in range(m):
if harta[i][j] == 1 and not visited[i][j]:
count += 1
dfs(i, j, n, m, harta, visited)
return count

def dfs(x, y, n, m, harta, visited):
if x < 0 or x >= n or y < 0 or y >= m or visited[x][y] or harta[x][y] == 0:
return
visited[x][y] = True
dfs(x-1, y, n, m, harta, visited)
dfs(x+1, y, n, m, harta, visited)
dfs(x, y-1, n, m, harta, visited)
dfs(x, y+1, n, m, harta, visited)

def main():
with open("fill.in") as f:
n, m = map(int, f.readline().split())
harta = [list(map(int, f.readline().split())) for i in range(n)]

if not validare(n, m, harta):
print("Date invalide")
return

with open("fill.out", "w") as f:
f.write(str(numar_continente(n, m, harta)))

if __name__ == '__main__':
main()

</syntaxhighlight>

==Explicații ==
Pentru a rezolva această problemă, putem folosi o variantă a algoritmului DFS (Depth-First Search) pentru a parcurge matricea. Pentru a număra continentele, vom căuta primul element 1 din matrice și vom căuta toate celulele adiacente cu acestea, marcate cu 1, folosind o căutare în adâncime.

În implementarea noastră, definim o funcție validare_matrice care verifică dacă matricea introdusă în fișierul de intrare este validă, adică are dimensiunile n și m, și are elemente doar 0 sau 1. În caz contrar, programul va afișa un mesaj de eroare.

Funcția rezolva primește matricea și dimensiunile acesteia și returnează numărul de continente găsite. Algoritmul DFS este implementat în funcția auxiliară dfs, care primește matricea, poziția curentă și o matrice booleană care urmărește celulele deja vizitate. Algoritmul parcurge matricea în profunzime și marchează celulele vizitate.

În funcția main citim dimensiunile matricei și matricea din fișierul de intrare. Apoi, verificăm dacă matricea este validă. Dacă este validă, apelăm funcția rezolva și afișăm rezultatul în fișierul de ieșire. În caz contrar, afișăm un mesaj de eroare.

Observăm că, pentru a urmări celulele vizitate în matricea de intrare, folosim o matrice suplimentară visited de dimensiune n x m, care conține valori booleane. Aceasta este utilă pentru a evita parcurgerea acelorași celule de mai multe ori.

0837 - Fill - Revision history

Catalin Moje at 20:38, 14 May 2023