Programozás‎ > ‎Feladatok‎ > ‎

Képátló

Adott egy N x N pixelből álló fekete-fehér kép. Szeretnénk a bal felső saroktól a jobb alsó sarokig egy jobbra-lefele haladó határvonalat húzni úgy, hogy a vonaltól jobbra-felfele eső fekete (0 értékű), valamint a vonaltól balra-lefele eső fehér (1 értékű) pixelek számának K összege a lehető legkevesebb legyen.  A határvonalra eső pixelek nem számítanak bele az összegbe (vehetjük úgy, hogy azokat töröltük).

Feladat

Írjunk programot, ami megadja K lehetséges minimumát és ki is rajzol egy optimális "vágást".

Bemenet

A bemenet első sora N értékét tartalmazza (1 < N <= 30). Ezután N sorban N karakter következik, a pixelek színe: 0 = fekete, 1 = fehér.

Kimenet

Az első sorába K lehetséges minimális értékét kell írni. Ezután N sorba a bemeneti táblát kell kiadni, de a vágás helyét szóközök jelölik.

Példa

Bemenet  Kimenet
5
11111
01110
10011
01110
01100
3
 1111
 1110
  011
0 110
0

5
11111
11111
00111
00110
00110
1
 1111
   11
00 11
00 10
00  

5
11111
01110
00011
00100
01101
3
 1111
   10
00 11
00  
0110

Tesztadatok

30x30-as bemenetek: atlo.zip
Minimumok: 237, 236, 251, 232, 220

Címkék

A feladat forrása: NTOITV 2011/2012 1. forduló, 5. feladat
Algoritmusok: dinamikus programozás