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
|