Algoritmus

Az OKTV útmutatónak megfelelően bevezetünk egy T[i,j] tömböt, ami azt fogja tartalmazni, hogy ha az (i,j) pontból kell az (N,N) pontba jobbra-lefele haladó átlót húznunk a feladat szabályai szerint, akkor mennyi a minimum. Két triviális és egy nem-triviális eset van. (i-t tekintjük a sor, j-t pedig az oszlop indexének.)

• ha i = N vagy j = N akkor T[i,j] = 0, hiszen a képátló kitölti a "téglalap" teljes egészét, nincsenek alatta és felette pixelek;
• egyébként T[i,j] = min{T[i+1,j]+S[i,j], T[i,j+1]+O[i,j]}, ahol S[i,j] az (i,j)-től jobbra levő 0-ák száma, O[i,j] pedig az (i,j) alatti 1-ek száma. (Ha lefele lépünk, akkor a mellettünk lévő "rossz" mezők számával nő a végösszeg, ha pedig jobbra, akkor az alattunk levő "rossz" mezők számával.)

Annyi további dolgunk van, hogy ha a T[i,j]-t a minimum kiválasztásával számoltuk ki, akkor fel kell jegyezni, hogy lefele vagy jobbra léptünk. Ehhez célszerű egy lépés[] tömböt használni. A bevezetett adatszerkezetben az a szép, hogy alulról fölfelé, jobbról balra egyértelműen kitölthető mindkét táblázat. Végül a minimális (optimális) érték T[1,1]-ben lesz. (Pascal-os tömbindexelés esetén.)

Kódok

Mezei Balázs (C++): mb_kepatlo.cpp
Ódor Gergő (C++): og_kepatlo.cpp
Erben Péter (java): ep_kepatlo.java (csak minimum, kirajzolás nélkül)