Bonte Lucas Gabriel at 23:24, 10 December 2023

2023-12-10T23:24:23Z

← Older revision		Revision as of 23:24, 10 December 2023
Line 5:		Line 5:
	==Date de intrare==		==Date de intrare==

	Fișierul de intrare '''~~plaja~~.in''' conține pe prima linie numerele '''n''' și '''m''', iar pe următoarele '''n''' linii câte '''m''' caractere reprezentând plaja.		Fișierul de intrare '''plajain.txt''' conține pe prima linie numerele '''n''' și '''m''', iar pe următoarele '''n''' linii câte '''m''' caractere reprezentând plaja.

	==Date de ieșire==		==Date de ieșire==

	Fișierul de ieșire '''~~plaja~~.~~out~~''' va conține pe prima linie numărul '''S''', reprezentând aria maximă a unui dreptunghi liber.		Fișierul de ieșire '''plajaout.txt''' va conține pe prima linie numărul '''S''', reprezentând aria maximă a unui dreptunghi liber.

	==Restricții și precizări==		==Restricții și precizări==
Line 15:		Line 15:
	*'''1 ≤ n, m ≤ 1000'''		*'''1 ≤ n, m ≤ 1000'''

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

	'''~~plaja~~.in'''		'''plajain.txt'''

	:5 5		5 5
	:11111		11111
	:11000		11000
	:11100		11100
	:11100		11100
	:11110		11110

	'''~~plaja~~.~~out~~'''		'''plajaout.txt'''

	:6		Datele de intrare corespund restrictiilor impuse
			6

			==Exemplul 2:==

			'''plajain.txt'''

			plaja

			'''plajaout.txt'''

			Datele de intrare nu corespund restrictiilor impuse

	==Explicație==		==Explicație==
Line 44:		Line 55:
	<syntaxhighlight lang="python" line="1" start="1">		<syntaxhighlight lang="python" line="1" start="1">

	~~# Functia max_rectangle calculeaza aria maxima a unui dreptunghi liber in matrice~~		def validare(matrice, n_linii, m_coloane): # functia de validare a datelor de intrare
	def ~~max_rectangle~~(~~matrix~~):		if not matrice:
	# ~~Daca matricea este goala, returnam 0~~		raise ValueError("Matricea este goala")
	if not ~~matrix~~:
	~~return 0~~

	m = len(~~matrix~~[0])		if not (1 <= n_linii <= 1000) or not (1 <= m_coloane <= 1000):
	~~# Initializam inaltimea fiecarui dreptunghi cu 0~~		raise ValueError("Valorile n sau m nu respecta restrictiile impuse")
	height = [0] * (m + 1)
			for row in matrice:
			if len(row) != m_coloane:
			raise ValueError("Lungimea randului nu este egala cu m")

			for element in row:
			if not element.isdigit(): # fiecare caracter trebuie sa fie cifra
			raise ValueError("Elementul matricei nu este o cifra")

			file_out.write("Datele de intrare corespund restrictiilor impuse\n")


			def max_rectangle(matrice): # functia de rezolvare
			m_coloane = len(matrice[0])
			height = [0] * (m_coloane + 1)
	ans = 0		ans = 0

	~~# Parcurgem fiecare rand din matrice~~		for row in matrice:
	for row in ~~matrix~~:		for i in range(m_coloane):
	for i in range(m):
	~~# Daca elementul este 0, crestem inaltimea dreptunghiului~~
	height[i] = height[i] + 1 if row[i] == '0' else 0		height[i] = height[i] + 1 if row[i] == '0' else 0
	stack = [-1]		stack = [-1]
	for i in range(m + 1):		for i in range(m_coloane + 1):
	~~# Cat timp inaltimea curenta este mai mica decat inaltimea din varful stivei~~
	while height[i] < height[stack[-1]]:		while height[i] < height[stack[-1]]:
	~~# Scoatem elementul din varful stivei si calculam aria dreptunghiului~~
	h = height[stack.pop()]		h = height[stack.pop()]
	w = i - 1 - stack[-1]		w = i - 1 - stack[-1]
	ans = max(ans, h * w)		ans = max(ans, h * w)
	~~# Adaugam inaltimea curenta in stiva~~
	stack.append(i)		stack.append(i)
	return ans		return ans

	~~# Functia main citeste datele de intrare, calculeaza aria maxima si scrie rezultatul in fisierul de iesire~~
	~~def main():~~
	~~with open('plaja.in', 'r') as file:~~
	~~n, m = map(int, file.readline().split())~~
	~~matrix = [list(file.readline().strip()) for _ in range(n)]~~
	~~area = max_rectangle(matrix)~~
	~~with open('plaja.out', 'w') as file:~~
	~~file.write(str(area))~~

	~~# Apelam functia main~~		if __name__ == '__main__':
	if __name__ == "~~__main__~~":		file_in = open('plajain.txt', 'r') # declararea fisierelor
	~~main~~()		file_out = open('plajaout.txt', 'w') # fisierul out trebuie declarat cu optiunea "w" (write)

			try:
			n, m = map(int, file_in.readline().split())
			matrix = [list(file_in.readline().strip()) for _ in range(n)]

			validare(matrix, n, m) # apelul functiei de validare
			area = max_rectangle(matrix) # apelul functiei de rezolvare
			file_out.write(str(area))

			except ValueError:
			file_out.write("Datele de intrare nu corespund restrictiilor impuse")
			except IndexError:
			file_out.write("Datele de intrare nu corespund restrictiilor impuse")

	</syntaxhighlight>		</syntaxhighlight>

Bonte Lucas Gabriel: Pagină nouă: ==Cerința== O plajă poate fi văzută ca o matrice cu '''n''' linii și '''m''' coloane. Elementele matricii sunt codificate cu '''0''', însemnând o poziție liberă, și '''1''', însemnând o poziție ocupată. Să se afle aria celui mai mare dreptunghi liber din matricea dată. ==Date de intrare== Fișierul de intrare '''plaja.in''' conține pe prima linie numerele '''n''' și '''m''', iar pe următoarele '''n''' linii câte '''m''' caractere reprezentând plaja. =...

2023-11-06T16:45:42Z

Pagină nouă: ==Cerința== O plajă poate fi văzută ca o matrice cu '''n''' linii și '''m''' coloane. Elementele matricii sunt codificate cu '''0''', însemnând o poziție liberă, și '''1''', însemnând o poziție ocupată. Să se afle aria celui mai mare dreptunghi liber din matricea dată. ==Date de intrare== Fișierul de intrare '''plaja.in''' conține pe prima linie numerele '''n''' și '''m''', iar pe următoarele '''n''' linii câte '''m''' caractere reprezentând plaja. =...

New page

==Cerința==

O plajă poate fi văzută ca o matrice cu '''n''' linii și '''m''' coloane. Elementele matricii sunt codificate cu '''0''', însemnând o poziție liberă, și '''1''', însemnând o poziție ocupată. Să se afle aria celui mai mare dreptunghi liber din matricea dată.

==Date de intrare==

Fișierul de intrare '''plaja.in''' conține pe prima linie numerele '''n''' și '''m''', iar pe următoarele '''n''' linii câte '''m''' caractere reprezentând plaja.

==Date de ieșire==

Fișierul de ieșire '''plaja.out''' va conține pe prima linie numărul '''S''', reprezentând aria maximă a unui dreptunghi liber.

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

*'''1 ≤ n, m ≤ 1000'''

==Exemplu:==

'''plaja.in'''

:5 5
:11111
:11000
:11100
:11100
:11110

'''plaja.out'''

:6

==Explicație==

1 1 1 1 1
1 1 0 '''0''' '''0'''
1 1 1 '''0''' '''0'''
1 1 1 '''0''' '''0'''
1 1 1 1 0

Suprafata dreptunghiulara de aria maxima este cea ingrosata.

==Rezolvare==

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

# Functia max_rectangle calculeaza aria maxima a unui dreptunghi liber in matrice
def max_rectangle(matrix):
# Daca matricea este goala, returnam 0
if not matrix:
return 0

m = len(matrix[0])
# Initializam inaltimea fiecarui dreptunghi cu 0
height = [0] * (m + 1)
ans = 0

# Parcurgem fiecare rand din matrice
for row in matrix:
for i in range(m):
# Daca elementul este 0, crestem inaltimea dreptunghiului
height[i] = height[i] + 1 if row[i] == '0' else 0
stack = [-1]
for i in range(m + 1):
# Cat timp inaltimea curenta este mai mica decat inaltimea din varful stivei
while height[i] < height[stack[-1]]:
# Scoatem elementul din varful stivei si calculam aria dreptunghiului
h = height[stack.pop()]
w = i - 1 - stack[-1]
ans = max(ans, h * w)
# Adaugam inaltimea curenta in stiva
stack.append(i)
return ans

# Functia main citeste datele de intrare, calculeaza aria maxima si scrie rezultatul in fisierul de iesire
def main():
with open('plaja.in', 'r') as file:
n, m = map(int, file.readline().split())
matrix = [list(file.readline().strip()) for _ in range(n)]
area = max_rectangle(matrix)
with open('plaja.out', 'w') as file:
file.write(str(area))

# Apelam functia main
if __name__ == "__main__":
main()

</syntaxhighlight>

1267 - plaja - Revision history

Bonte Lucas Gabriel at 23:24, 10 December 2023