0844 - Croco1: Difference between revisions
Catalin Moje (talk | contribs) Pagină nouă: ==Cerința== Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unui lac, în care 0 înseamnă uscat, iar 1 înseamnă apă. Se dorește plasarea pe fiecare zonă cu uscat a unui crocodil sau a unui elefant astfel încât să nu fie două animale din aceeași specie în zone învecinate. În plus, se dorește ca numărul de crocodil să fie cât mai mare. Să se determine câți crocodili și câți elefanți se pot plasa pe lac, astfel... |
Catalin Moje (talk | contribs) No edit summary |
||
Line 14: | Line 14: | ||
==Restricții și precizări== | ==Restricții și precizări== | ||
≤ n , m ≤ 100 | *≤ n , m ≤ 100 | ||
==Exemplu== | ==Exemplu== | ||
===Exemplu1=== | ===Exemplu1=== | ||
:Intrare: | |||
croco1.in | ;croco1.in | ||
;3 5 | |||
3 5 | ;0 0 0 1 0 | ||
0 0 0 1 0 | ;0 0 1 0 0 | ||
0 0 1 0 0 | ;1 0 0 1 0 | ||
1 0 0 1 0 | :Iesire: | ||
;croco1.out | |||
;7 4 | |||
croco1.out | |||
7 4 | |||
==Rezolvare== | ==Rezolvare== | ||
<syntaxhighlight lang="python" line="1"> | |||
def valideaza_matrice(matrice): | def valideaza_matrice(matrice): | ||
Line 87: | Line 83: | ||
==Explicații == | ==Explicații == | ||
Funcția validare() verifică dacă matricea dată este validă conform cerințelor problemei și returnează False dacă matricea nu respectă restricțiile sau conține elemente care nu sunt 0 sau 1. Funcția rezolva_crocodili() implementează algoritmul greedy pentru a plasa crocodili în zonele de uscat ale matricei. Algoritmul începe parcurgerea matricei de la stânga sus și verifică dacă fiecare element este 0 (adica este uscat). Dacă este, atunci verifică dacă elementul poate fi ocupat de un crocodil. Un element poate fi ocupat de un crocodil dacă toate elementele vecine imediate ale sale (în sus, jos, stânga și dreapta) nu sunt ocupate de crocodili. Dacă elementul poate fi ocupat de un crocodil, atunci se marchează elementul ca fiind ocupat de un crocodil și se crește numărul de crocodili cu 1. După ce s-au plasat toți crocodilii, numărul de elefanți se poate determina prin numărarea elementelor rămase neocupate din matrice. | #1 Funcția validare() verifică dacă matricea dată este validă conform cerințelor problemei și returnează False dacă matricea nu respectă restricțiile sau conține elemente care nu sunt 0 sau 1. | ||
#2 Funcția rezolva_crocodili() implementează algoritmul greedy pentru a plasa crocodili în zonele de uscat ale matricei. Algoritmul începe parcurgerea matricei de la stânga sus și verifică dacă fiecare element este 0 (adica este uscat). Dacă este, atunci verifică dacă elementul poate fi ocupat de un crocodil. Un element poate fi ocupat de un crocodil dacă toate elementele vecine imediate ale sale (în sus, jos, stânga și dreapta) nu sunt ocupate de crocodili. Dacă elementul poate fi ocupat de un crocodil, atunci se marchează elementul ca fiind ocupat de un crocodil și se crește numărul de crocodili cu 1. După ce s-au plasat toți crocodilii, numărul de elefanți se poate determina prin numărarea elementelor rămase neocupate din matrice. | |||
Funcția main() deschide fișierul de intrare, citește dimensiunile matricei și matricea însăși, validează matricea cu ajutorul funcției validare(), rezolvă problema cu ajutorul funcției rezolva_crocodili(), și scrie rezultatele în fișierul de ieșire. | #3 Funcția main() deschide fișierul de intrare, citește dimensiunile matricei și matricea însăși, validează matricea cu ajutorul funcției validare(), rezolvă problema cu ajutorul funcției rezolva_crocodili(), și scrie rezultatele în fișierul de ieșire. |
Latest revision as of 20:57, 14 May 2023
Cerința[edit | edit source]
Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unui lac, în care 0 înseamnă uscat, iar 1 înseamnă apă.
Se dorește plasarea pe fiecare zonă cu uscat a unui crocodil sau a unui elefant astfel încât să nu fie două animale din aceeași specie în zone învecinate. În plus, se dorește ca numărul de crocodil să fie cât mai mare.
Să se determine câți crocodili și câți elefanți se pot plasa pe lac, astfel încât numărul de crocodili să fie cât mai mare.
Date de intrare[edit | edit source]
ișierul de intrare croco1.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[edit | edit source]
Fișierul de ieșire croco1.out va conține pe prima linie numerele C E, reprezentând numărul de crocodili, respectiv numărul de elefanți care pot fi plasați în condițiile precizate, astfel încât numărul de crocodili să fie cât mai mare.
Restricții și precizări[edit | edit source]
*≤ n , m ≤ 100
Exemplu[edit | edit source]
Exemplu1[edit | edit source]
- Intrare:
- croco1.in
- 3 5
- 0 0 0 1 0
- 0 0 1 0 0
- 1 0 0 1 0
- Iesire:
- croco1.out
- 7 4
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line="1">
def valideaza_matrice(matrice):
for linie in matrice: if len(linie) != len(matrice[0]): return False for element in linie: if element != 0 and element != 1: return False return True
def rezolva_crocodili(matrice):
nr_crocodili = 0 nr_elefanti = 0 directii = [(0, -1), (-1, 0), (0, 1), (1, 0)] for i in range(len(matrice)): for j in range(len(matrice[0])): if matrice[i][j] == 0: poate_fi_croc = True for dx, dy in directii: x, y = i + dx, j + dy if 0 <= x < len(matrice) and 0 <= y < len(matrice[0]): if matrice[x][y] == 2: poate_fi_croc = False break if poate_fi_croc: matrice[i][j] = 2 nr_crocodili += 1 nr_elefanti = sum(linie.count(0) for linie in matrice) return nr_crocodili, nr_elefanti
def main():
with open("croco1.in") as f: n, m = map(int, f.readline().split()) matrice = [list(map(int, f.readline().split())) for _ in range(n)] if not valideaza_matrice(matrice): print("Matricea data nu este valida.") return nr_crocodili, nr_elefanti = rezolva_crocodili(matrice) with open("croco1.out", "w") as f: f.write(f"{nr_crocodili} {nr_elefanti}\n")
if __name__ == "__main__":
main()
</syntaxhighlight>
Explicații[edit | edit source]
- 1 Funcția validare() verifică dacă matricea dată este validă conform cerințelor problemei și returnează False dacă matricea nu respectă restricțiile sau conține elemente care nu sunt 0 sau 1.
- 2 Funcția rezolva_crocodili() implementează algoritmul greedy pentru a plasa crocodili în zonele de uscat ale matricei. Algoritmul începe parcurgerea matricei de la stânga sus și verifică dacă fiecare element este 0 (adica este uscat). Dacă este, atunci verifică dacă elementul poate fi ocupat de un crocodil. Un element poate fi ocupat de un crocodil dacă toate elementele vecine imediate ale sale (în sus, jos, stânga și dreapta) nu sunt ocupate de crocodili. Dacă elementul poate fi ocupat de un crocodil, atunci se marchează elementul ca fiind ocupat de un crocodil și se crește numărul de crocodili cu 1. După ce s-au plasat toți crocodilii, numărul de elefanți se poate determina prin numărarea elementelor rămase neocupate din matrice.
- 3 Funcția main() deschide fișierul de intrare, citește dimensiunile matricei și matricea însăși, validează matricea cu ajutorul funcției validare(), rezolvă problema cu ajutorul funcției rezolva_crocodili(), și scrie rezultatele în fișierul de ieșire.