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ă. În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse.", iar daca se indeplinesc se afiseaza mesajul "Datele de intrare corespund restricțiilor impuse."

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

Exemplul 2

Intrare

0 1

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

def citeste_poza():
    try:
        n, m = map(int, input("Introduceți numărul de linii și coloane (1 ≤ n,m ≤ 100): ").split())

        # Verificăm dacă dimensiunile respectă restricțiile
        if not (1 <= n <= 100 and 1 <= m <= 100):
            raise ValueError("Datele de intrare nu corespund restricțiilor impuse.")

        poza = []
        prim_plan_gasit = False

        for i in range(n):
            linie = list(map(int, input().split()))

            # Verificăm dacă există cel puțin un element de prim-plan
            if 1 in linie:
                prim_plan_gasit = True

            poza.append(linie)

        # Dacă nu există elemente de prim-plan, afisam o excepție
        if not prim_plan_gasit:
            raise ValueError("În poză trebuie să existe cel puțin un element de prim-plan.")

        print("Datele de intrare corespund restricțiilor impuse.")
        return poza
    except ValueError as ve:
        print(ve)
        exit()

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.