0597 - Poza

Cerinţa

Fie o poză dată sub forma unei matrice cu n linii și m coloane, în care elementele sunt 0 sau 1: un element 0 reprezintă fundalul imaginii, iar un element 1 reprezintă obiect din prim plan. Este necesară tăierea unei bucăți din imagine astfel încât:
- laturile bucății tăiate sunt paralele cu laturile pozei inițiale și cât mai mici;
- toate obiectele din prim-plan în poza inițială apar în poza tăiată; Determinați dimensiunile pozei tăiate, precum și conținutul ei.

Date de intrare

Programul citește de la tastatură numerele n m, iar apoi n șiruri cu câte m valori 0 sau 1, reprezentând poza inițială.

Date de ieșire

Programul va afișa pe ecran numerele p q, separate printr-un spațiu, reprezentând dimensiunile pozei tăiate, apoi p linii cu câte q valori separate prin exact un spațiu, reprezentând poza tăiată.

Restricţii şi precizări

• 1 ≤ n, m ⩽ 100

în poză va exista cel puțin un element de prim-plan

Exemplul 1

Intrare

5 6
0 0 0 0 0 0
0 0 1 0 1 0
0 1 1 1 1 1
0 0 0 0 1 0
0 0 0 0 0 0

Ieșire

3 5
0 1 0 1 0
1 1 1 1 1
0 0 0 1 0

Rezolvare

<syntaxhighlight lang="python" line>

def citeste_poza():
   n, m = map(int, input("Introduceți numărul de linii și coloane (1 ≤ n,m ≤ 100): ").split())
   poza = []
   for _ in range(n):
       linie = list(map(int, input().split()))
       poza.append(linie)
   return poza

def taie_poza(poza):

   min_linie, max_linie, min_coloana, max_coloana = n, 0, m, 0
   for i in range(n):
       for j in range(m):
           if poza[i][j] == 1:
               min_linie = min(min_linie, i)
               max_linie = max(max_linie, i)
               min_coloana = min(min_coloana, j)
               max_coloana = max(max_coloana, j)
   p = max_linie - min_linie + 1
   q = max_coloana - min_coloana + 1
   poza_taiata = [poza[i][min_coloana:max_coloana + 1] for i in range(min_linie, max_linie + 1)]
   return p, q, poza_taiata

if __name__ == "__main__":

   poza = citeste_poza()
   n, m = len(poza), len(poza[0])
   p, q, poza_taiata = taie_poza(poza)
   print(p, q)
   for linie in poza_taiata:
       print(*linie)

</syntaxhighlight>

Explicație

Programul începe prin citirea dimensiunilor și matricei pozei inițiale, asigurându-se că sunt respectate restricțiile (1 ≤ n, m ≤ 100) . Apoi, găsește coordonatele colțurilor dreptunghiului care acoperă obiectele în prim-plan, determinând astfel dimensiunile pozei tăiate (p și q). Poza tăiată este extrasă din poza inițială și afișată la consolă împreună cu dimensiunile sale.