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).

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

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.

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.

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

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

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

Algoritmusok: dinamikus programozás