Bonte Lucas Gabriel at 21:12, 12 December 2023

2023-12-12T21:12:45Z

← Older revision		Revision as of 21:12, 12 December 2023
Line 22:		Line 22:
	*Pentru '''40''' de puncte, '''n,m≤40'''		*Pentru '''40''' de puncte, '''n,m≤40'''

	==~~Exemplu~~:==		==Exemplul 1:==

	;Intrare		;Intrare

	:8 9		8 9
	:1 1 1 1 1 1 1 1 1		1 1 1 1 1 1 1 1 1
	:1 1 4 4 1 3 3 3 3		1 1 4 4 1 3 3 3 3
	:1 4 4 4 3 3 3 3 3		1 4 4 4 3 3 3 3 3
	:1 4 4 4 3 3 3 3 3		1 4 4 4 3 3 3 3 3
	:1 2 1 1 3 3 3 3 3		1 2 1 1 3 3 3 3 3
	:2 2 2 1 1 3 3 3 3		2 2 2 1 1 3 3 3 3
	:4 2 2 2 2 2 2 3 3		4 2 2 2 2 2 2 3 3
	:4 4 2 2 2 2 2 3 3		4 4 2 2 2 2 2 3 3

	;Ieșire		;Ieșire

	:2 1 0 0 1 0 0 0 0		Datele de intrare corespund restrictiilor impuse.
	:1 0 0 0 0 0 0 0 0		2 1 0 0 1 0 0 0 0
	:0 0 1 0 0 1 1 1 1		1 0 0 0 0 0 0 0 0
	:0 0 0 0 0 1 2 2 2		0 0 1 0 0 1 1 1 1
	:0 0 0 0 0 1 1 2 3		0 0 0 0 0 1 2 2 2
	:0 1 0 0 0 0 0 1 2		0 0 0 0 0 1 1 2 3
	:0 0 1 0 0 0 0 0 1		0 1 0 0 0 0 0 1 2
	:1 0 0 1 1 1 0 0 1		0 0 1 0 0 0 0 0 1
			1 0 0 1 1 1 0 0 1

			==Exemplul 2:==

			;Intrare

			emigrare

			;Ieșire

			Datele de intrare nu corespund restrictiilor impuse.

	==Explicație==		==Explicație==

	Cele 4 țări sunt reprezentate de valorile 1, 2, 3, 4.		Cele '''4''' țări sunt reprezentate de valorile '''1, 2, 3, 4.'''

	==Rezolvare==		==Rezolvare==
Line 57:		Line 68:
	from collections import deque		from collections import deque

	def ~~min_distance~~(n, ~~m, matrix~~):
	~~# Definim directiile in care putem merge~~ (~~sus, jos~~, ~~stanga~~, ~~dreapta~~)		def verificare_restrictii(nr_n, nr_m): # functia de verificare a datelor de intrare
			if 2 <= nr_n <= 103 and 2 <= nr_m <= 103:
			return True
			else:
			return False


			def min_distance(nr_n, nr_m, matrice):
	dx = [-1, 0, 1, 0]		dx = [-1, 0, 1, 0]
	dy = [0, 1, 0, -1]		dy = [0, 1, 0, -1]

	~~# Initializam o matrice de vizitare si o matrice de distante~~		visited = [[False] * nr_m for _ in range(nr_n)]
	visited = [[False]*m for _ in range(n)]		distanta = [[0] * nr_m for _ in range(nr_n)]
	~~dist~~ = [[0]*m for _ in range(n)]

	~~# Cream o coada pentru BFS~~
	q = deque()		q = deque()

	~~# Parcurgem matricea si adaugam in coada toate celulele care au cel putin un vecin cu valoare diferita~~		for i in range(nr_n):
	for i in range(n):		for j in range(nr_m):
	for j in range(m):		if any(matrice[i][j] != matrice[i + dx[k]][j + dy[k]] for k in range(4) if 0 <= i + dx[k] < nr_n and 0 <= j + dy[k] < nr_m):
	if any(~~matrix~~[i][j] != ~~matrix~~[i+dx[k]][j+dy[k]] for k in range(4) if 0 <= i+dx[k] < n and 0 <= j+dy[k] < m):
	q.append((i, j))		q.append((i, j))
	visited[i][j] = True		visited[i][j] = True

	~~# Parcurgem coada si actualizam distantele pentru toate celulele nevizitate~~
	while q:		while q:
	x, y = q.popleft()		x, y = q.popleft()
	for k in range(4):		for k in range(4):
	nx, ny = x + dx[k], y + dy[k]		nx, ny = x + dx[k], y + dy[k]
	if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:		if 0 <= nx < nr_n and 0 <= ny < nr_m and not visited[nx][ny]:
	~~dist~~[nx][ny] = ~~dist~~[x][y] + 1		distanta[nx][ny] = distanta[x][y] + 1
	q.append((nx, ny))		q.append((nx, ny))
	visited[nx][ny] = True		visited[nx][ny] = True

	return ~~dist~~		return distanta

			# Rularea se face in felul urmator, se scrie de la tastatura 8, apoi 9, apoi toata matricea

	~~# Citim dimensiunile matricei si matricea~~
	~~n, m = map(int, input().split())~~
	~~matrix = [list(map(int, input().split())) for _ in range(n)]~~

	~~# Calculam distantele minime~~		if __name__ == '__main__':
	~~dist~~ = ~~min_distance~~(n, m~~, matrix~~)		try:
			n = int(input("Introduceti numarul de linii: "))
			m = int(input("Introduceti numarul de coloane: "))

	~~# Afisam distantele~~		if verificare_restrictii(n, m):
	for row in dist:		print("Datele de intrare corespund restrictiilor impuse.")
	print(*row)		matrix = [list(map(int, input().split())) for _ in range(n)]
			dist = min_distance(n, m, matrix)
			for row in dist:
			print(*row)
			else:
			print("Datele de intrare nu corespund restrictiilor impuse.")
			except ValueError:
			print("Datele de intrare nu corespund restrictiilor impuse.")
			except IndexError:
			print("Datele de intrare nu corespund restrictiilor impuse.")

	</syntaxhighlight>		</syntaxhighlight>

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== Tărâmul emigranților se poate reprezenta printr-o matrice de dimensiuni '''n×m'''. O țară este formată din toate celulele care au o anumită valoare. În fiecare celulă locuiește un om. Pe tărâmul emigranților fiecare om este nemulțumit și vrea să ajungă în orice altă țară în cel mai scurt timp posibil. Calculați pentru fiecare celulă distanța minimă până la o celulă de valoare diferită. ==Date de intrare== Pe prima linie se află...

2023-11-06T19:47:40Z

Pagină nouă: ==Cerința== Tărâmul emigranților se poate reprezenta printr-o matrice de dimensiuni '''n×m'''. O țară este formată din toate celulele care au o anumită valoare. În fiecare celulă locuiește un om. Pe tărâmul emigranților fiecare om este nemulțumit și vrea să ajungă în orice altă țară în cel mai scurt timp posibil. Calculați pentru fiecare celulă distanța minimă până la o celulă de valoare diferită. ==Date de intrare== Pe prima linie se află...

New page

==Cerința==

Tărâmul emigranților se poate reprezenta printr-o matrice de dimensiuni '''n×m'''. O țară este formată din toate celulele care au o anumită valoare. În fiecare celulă locuiește un om. Pe tărâmul emigranților fiecare om este nemulțumit și vrea să ajungă în orice altă țară în cel mai scurt timp posibil.

Calculați pentru fiecare celulă distanța minimă până la o celulă de valoare diferită.

==Date de intrare==

Pe prima linie se află numerele '''n''' și '''m'''. Pe a '''i'''-a dintre următoarele '''n''' linii se găsește o secvență de '''m''' numere. Al '''j'''-lea număr se notează '''ai,j''' și reprezintă țara din care face parte celula '''(i,j)'''
.

==Date de ieșire==

Se vor afișa '''nm''' numere naturale reprezenând distanțele pentru fiecare om în parte. Pe a '''i'''-a dintre cele '''n''' linii se găsește o secvență de '''m''' numere. Al '''j'''-lea număr se notează '''di,j''' și reprezintă distanța minimă ce trebuie să o parcurgă omul din celula '''(i,j)''' pentru a ajunge în altă țară.

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

*'''2≤n,m≤10^3'''
*Se garantează că există cel puțin două țări
*Celulele unei țări nu sunt neapărat conectate
*Pentru '''20''' de puncte, '''n,m≤10'''
*Pentru '''40''' de puncte, '''n,m≤40'''

==Exemplu:==

;Intrare

:8 9
:1 1 1 1 1 1 1 1 1
:1 1 4 4 1 3 3 3 3
:1 4 4 4 3 3 3 3 3
:1 4 4 4 3 3 3 3 3
:1 2 1 1 3 3 3 3 3
:2 2 2 1 1 3 3 3 3
:4 2 2 2 2 2 2 3 3
:4 4 2 2 2 2 2 3 3

;Ieșire

:2 1 0 0 1 0 0 0 0
:1 0 0 0 0 0 0 0 0
:0 0 1 0 0 1 1 1 1
:0 0 0 0 0 1 2 2 2
:0 0 0 0 0 1 1 2 3
:0 1 0 0 0 0 0 1 2
:0 0 1 0 0 0 0 0 1
:1 0 0 1 1 1 0 0 1

==Explicație==

Cele 4 țări sunt reprezentate de valorile 1, 2, 3, 4.

==Rezolvare==

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

from collections import deque

def min_distance(n, m, matrix):
# Definim directiile in care putem merge (sus, jos, stanga, dreapta)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# Initializam o matrice de vizitare si o matrice de distante
visited = [[False]*m for _ in range(n)]
dist = [[0]*m for _ in range(n)]

# Cream o coada pentru BFS
q = deque()

# Parcurgem matricea si adaugam in coada toate celulele care au cel putin un vecin cu valoare diferita
for i in range(n):
for j in range(m):
if any(matrix[i][j] != matrix[i+dx[k]][j+dy[k]] for k in range(4) if 0 <= i+dx[k] < n and 0 <= j+dy[k] < m):
q.append((i, j))
visited[i][j] = True

# Parcurgem coada si actualizam distantele pentru toate celulele nevizitate
while q:
x, y = q.popleft()
for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
dist[nx][ny] = dist[x][y] + 1
q.append((nx, ny))
visited[nx][ny] = True

return dist

# Citim dimensiunile matricei si matricea
n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]

# Calculam distantele minime
dist = min_distance(n, m, matrix)

# Afisam distantele
for row in dist:
print(*row)

</syntaxhighlight>

4052 - emigrare - Revision history

Bonte Lucas Gabriel at 21:12, 12 December 2023