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

Exemplu 2

Intrare

3 4

1 0 1 0

0 0 0 0

1 1 1 1

Ieșire

3 4

1 0 1 0

0 0 0 0

1 1 1 1

Rezolvare

 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)

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.