2724 - LSQ - Revision history

Cata at 07:02, 3 May 2023

2023-05-03T07:02:14Z

← Older revision		Revision as of 07:02, 3 May 2023
Line 77:		Line 77:
	return 1 <= n <= 1000 and 1 <= m <= 1000		return 1 <= n <= 1000 and 1 <= m <= 1000

	~~def main()~~:		if __name__ == "__main__":
	with open("lsq.in", "r") as fin, open("lsq.out", "w") as fout:		with open("lsq.in", "r") as fin, open("lsq.out", "w") as fout:
	N, M = map(int, fin.readline().split())		N, M = map(int, fin.readline().split())
Line 88:		Line 88:
	ans = find_largest_square(N, M, A)		ans = find_largest_square(N, M, A)
	fout.write(str(ans) + "\n")		fout.write(str(ans) + "\n")


	~~if __name__ == "__main__":~~
	~~main()~~

	</syntaxhighlight>		</syntaxhighlight>
Line 104:		Line 100:
	Funcția `find_largest_square` parcurge fiecare celulă din matricea de intrare și, pentru fiecare celulă, verifică dacă poate fi colțul stânga-sus al unui pătrat și, în caz afirmativ, încearcă să-l mărească progresiv până la limita minimă dintre lungimile segmentelor de cifra 1 din matricile `LDL`, `CDL`, `LRU` și `CRU`.		Funcția `find_largest_square` parcurge fiecare celulă din matricea de intrare și, pentru fiecare celulă, verifică dacă poate fi colțul stânga-sus al unui pătrat și, în caz afirmativ, încearcă să-l mărească progresiv până la limita minimă dintre lungimile segmentelor de cifra 1 din matricile `LDL`, `CDL`, `LRU` și `CRU`.

	Funcția `validate_input` verifică dacă dimensiunile matricei de intrare sunt între 1 și 1000 inclusiv, iar ~~funcția~~ `~~main~~` citește datele de intrare din fișierul "lsq.in", validează dimensiunile matricei de intrare, calculează dimensiunea celui mai mare pătrat de cifra 1 și scrie rezultatul în fișierul "lsq.out".		Funcția `validate_input` verifică dacă dimensiunile matricei de intrare sunt între 1 și 1000 inclusiv, iar blocul `if __name__ == "__main__":` citește datele de intrare din fișierul "lsq.in", validează dimensiunile matricei de intrare, calculează dimensiunea celui mai mare pătrat de cifra 1 și scrie rezultatul în fișierul "lsq.out".

Cata at 07:01, 3 May 2023

2023-05-03T07:01:09Z

← Older revision		Revision as of 07:01, 3 May 2023
Line 6:		Line 6:

	==Date de ieșire==		==Date de ieșire==
	Fișierul de ieșire lsq.out va conține pe prima linie numărul L, reprezentând lungimea maximă a laturii unui pătrat ce conține doar 1 pe marginea sa.		Fișierul de ieșire lsq.out va conține pe prima linie numărul L, reprezentând lungimea maximă a laturii unui pătrat ce conține doar 1 pe marginea sa. Consola va afișa un mesaj de validare a datelor ("Input valid" sau "Input invalid" după caz).

	==Restricții și precizări==		==Restricții și precizări==
Line 26:		Line 26:
	: 4		: 4
	; Consola		; Consola
	: ~~Valid input~~		: Input valid
	==Explicație==		==Explicație==

Line 82:		Line 82:
	A = [list(map(int, fin.readline().strip())) for _ in range(N)]		A = [list(map(int, fin.readline().strip())) for _ in range(N)]
	if not validate_input(N, M):		if not validate_input(N, M):
	print("~~Invalid input!~~")		print("Input invalid")
	return		return
	else:		else:
	print("~~Valid input~~")		print("Input valid")
	ans = find_largest_square(N, M, A)		ans = find_largest_square(N, M, A)
	fout.write(str(ans) + "\n")		fout.write(str(ans) + "\n")
Line 96:		Line 96:

	==Explicație cod==		==Explicație cod==
	~~Acesta este un~~ program ~~Python care~~ calculează dimensiunea celui mai mare pătrat ~~complet~~ format din ~~cifrele de~~ 1 ~~dintr~~-o matrice dată. Matricea este dată ca o listă de liste de cifre. Algoritmul folosit pentru a găsi răspunsul constă în calcularea a patru matrice auxiliare, folosind programarea dinamică pentru a calcula lungimea celui mai mare pătrat posibil cu colțul din stânga sus la poziția curentă. Apoi, se parcurge matricea și se caută cel mai mare pătrat complet, verificând dacă toate cele patru laturi au o lungime cel puțin egală cu dimensiunea pătratului. În caz afirmativ, se actualizează dimensiunea maximă a pătratului.		Acest program calculează dimensiunea celui mai mare pătrat format numai din cifra 1 într-o matrice bidimensională dată.

	Funcția ~~validate_input()~~ verifică dacă ~~intrarea este validă~~, ~~adică~~ dacă ~~dimensiunea~~ matricei ~~se află~~ între 1 și 1000 inclusiv~~. Funcția~~ main() citește ~~matricea~~ din fișierul "lsq.in", validează ~~intrarea și apoi~~ calculează ~~și scrie~~ dimensiunea celui mai mare pătrat ~~complet~~ în fișierul "lsq.out".		Funcția `compute_matrices` calculează patru matrici: `LDL`, `CDL`, `LRU`, `CRU`, fiecare fiind de aceeași dimensiune ca matricea de intrare `A`. Matricile `LDL` și `CDL` conțin lungimile celor mai lungi segmente consecutive de cifra 1 din stânga și, respectiv, de sus de fiecare celulă, iar matricile `LRU` și `CRU` conțin lungimile celor mai lungi segmente consecutive de cifra 1 din dreapta și, respectiv, de jos de fiecare celulă.

			În denumirea matricelor din funcția `compute_matrices`, primele trei litere reprezintă inițialele direcțiilor de la care începe numărătoarea segmentelor de cifra 1. Astfel, matricea `LDL` conține lungimile segmentelor consecutive de cifra 1 din stânga fiecărei celule, începând de la stânga și mergând spre dreapta, matricea `CDL` conține lungimile segmentelor consecutive de cifra 1 de sus fiecărei celule, începând de sus și mergând în jos, iar matricea `LRU` conține lungimile segmentelor consecutive de cifra 1 din dreapta fiecărei celule, începând de la dreapta și mergând spre stânga, iar matricea `CRU` conține lungimile segmentelor consecutive de cifra 1 de jos fiecărei celule, începând de jos și mergând în sus.

			Funcția `find_largest_square` parcurge fiecare celulă din matricea de intrare și, pentru fiecare celulă, verifică dacă poate fi colțul stânga-sus al unui pătrat și, în caz afirmativ, încearcă să-l mărească progresiv până la limita minimă dintre lungimile segmentelor de cifra 1 din matricile `LDL`, `CDL`, `LRU` și `CRU`.

			Funcția `validate_input` verifică dacă dimensiunile matricei de intrare sunt între 1 și 1000 inclusiv, iar funcția `main` citește datele de intrare din fișierul "lsq.in", validează dimensiunile matricei de intrare, calculează dimensiunea celui mai mare pătrat de cifra 1 și scrie rezultatul în fișierul "lsq.out".

Cata at 08:00, 28 April 2023

2023-04-28T08:00:49Z

← Older revision		Revision as of 08:00, 28 April 2023
Line 12:		Line 12:
	* Se consideră pătrat și cel de latură 1 (conține doar un element).		* Se consideră pătrat și cel de latură 1 (conține doar un element).
	==Exemplu==		==Exemplu==
	lsq.in		; lsq.in

	7 7		: 7 7
	0000000		: 0000000
	0111100		: 0111100
	0101111		: 0101111
	0100101		: 0100101
	0111111		: 0111111
	0000011		: 0000011
	0000011		: 0000011
	lsq.out		; lsq.out

	4		: 4
			; Consola
			: Valid input
	==Explicație==		==Explicație==

Line 82:		Line 84:
	print("Invalid input!")		print("Invalid input!")
	return		return
			else:
			print("Valid input")
	ans = find_largest_square(N, M, A)		ans = find_largest_square(N, M, A)
	fout.write(str(ans) + "\n")		fout.write(str(ans) + "\n")

Cata: Pagină nouă: ==Cerința== Se dă o matrice binară (valori 0 și 1). Să se determine care este latura maximă a unui pătrat cu proprietatea că acesta are pe marginea sa doar valori 1. ==Date de intrare== Fișierul de intrare lsq.in conține pe prima linie numerele N și M, reprezentând numărul de linii și numărul de coloane ale matricei, apoi N linii, pe fiecare câte M valori 0 sau 1, neseparate prin niciun spațiu, reprezentând elementele matricei.. ==Date de ieșire== Fișier...

2023-04-20T19:28:44Z

Pagină nouă: ==Cerința== Se dă o matrice binară (valori 0 și 1). Să se determine care este latura maximă a unui pătrat cu proprietatea că acesta are pe marginea sa doar valori 1. ==Date de intrare== Fișierul de intrare lsq.in conține pe prima linie numerele N și M, reprezentând numărul de linii și numărul de coloane ale matricei, apoi N linii, pe fiecare câte M valori 0 sau 1, neseparate prin niciun spațiu, reprezentând elementele matricei.. ==Date de ieșire== Fișier...

New page

==Cerința==
Se dă o matrice binară (valori 0 și 1). Să se determine care este latura maximă a unui pătrat cu proprietatea că acesta are pe marginea sa doar valori 1.

==Date de intrare==
Fișierul de intrare lsq.in conține pe prima linie numerele N și M, reprezentând numărul de linii și numărul de coloane ale matricei, apoi N linii, pe fiecare câte M valori 0 sau 1, neseparate prin niciun spațiu, reprezentând elementele matricei..

==Date de ieșire==
Fișierul de ieșire lsq.out va conține pe prima linie numărul L, reprezentând lungimea maximă a laturii unui pătrat ce conține doar 1 pe marginea sa.

==Restricții și precizări==
* 1 &les; N, M &les; 1000
* Se consideră pătrat și cel de latură 1 (conține doar un element).
==Exemplu==
lsq.in

7 7
0000000
0111100
0101111
0100101
0111111
0000011
0000011
lsq.out

4
==Explicație==

0 0 0 0 0 0 0 
0 1 1 1 1 0 0 
0 1 0 1 1 1 1 
0 1 0 0 1 0 1 
0 1 1 1 1 1 1 
0 0 0 0 0 1 1 
0 0 0 0 0 1 1 

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

def compute_matrices(N, M, A):
LDL = [[0] * M for _ in range(N)]
CDL = [[0] * M for _ in range(N)]
LRU = [[0] * M for _ in range(N)]
CRU = [[0] * M for _ in range(N)]

for i in range(N):
for j in range(M):
if A[i][j] == 1:
LDL[i][j] = 1 + LDL[i][j - 1] if j > 0 else 1
CDL[i][j] = 1 + CDL[i - 1][j] if i > 0 else 1

for i in range(N - 1, -1, -1):
for j in range(M - 1, -1, -1):
if A[i][j] == 1:
LRU[i][j] = 1 + LRU[i][j + 1] if j < M - 1 else 1
CRU[i][j] = 1 + CRU[i + 1][j] if i < N - 1 else 1

return LDL, CDL, LRU, CRU

def find_largest_square(N, M, A):
LDL, CDL, LRU, CRU = compute_matrices(N, M, A)
ans = 0
for i in range(N):
for j in range(M):
for L in range(min(LDL[i][j], CDL[i][j]), ans, -1):
if L <= min(LRU[i - L + 1][j - L + 1], CRU[i - L + 1][j - L + 1]):
ans = L
break
return ans

def validate_input(n: int, m: int) -> bool:
return 1 <= n <= 1000 and 1 <= m <= 1000

def main():
with open("lsq.in", "r") as fin, open("lsq.out", "w") as fout:
N, M = map(int, fin.readline().split())
A = [list(map(int, fin.readline().strip())) for _ in range(N)]
if not validate_input(N, M):
print("Invalid input!")
return
ans = find_largest_square(N, M, A)
fout.write(str(ans) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

==Explicație cod==
Acesta este un program Python care calculează dimensiunea celui mai mare pătrat complet format din cifrele de 1 dintr-o matrice dată. Matricea este dată ca o listă de liste de cifre. Algoritmul folosit pentru a găsi răspunsul constă în calcularea a patru matrice auxiliare, folosind programarea dinamică pentru a calcula lungimea celui mai mare pătrat posibil cu colțul din stânga sus la poziția curentă. Apoi, se parcurge matricea și se caută cel mai mare pătrat complet, verificând dacă toate cele patru laturi au o lungime cel puțin egală cu dimensiunea pătratului. În caz afirmativ, se actualizează dimensiunea maximă a pătratului.

Funcția validate_input() verifică dacă intrarea este validă, adică dacă dimensiunea matricei se află între 1 și 1000 inclusiv. Funcția main() citește matricea din fișierul "lsq.in", validează intrarea și apoi calculează și scrie dimensiunea celui mai mare pătrat complet în fișierul "lsq.out".