Lösungsskizze Art College
=========================

Wir suchen zuerst nach dem Pinselstrich, der ganz am Ende gemalt wurde. Dies muss eine Zeile oder Spalte des Bildes sein, die nur aus einer einzigen Farbe besteht. Finden wir keine solche Zeile oder Spalte, brechen wir mit 'fake' ab. Sonst versuchen wir diesen letzten Strich rückgängig zu machen indem wir ihn mit Nullen überschreiben. Wir können uns diese Nullen als Fragezeichen vorstellen, mit der Bedeutung "Vor dem letzten Strich, kann dort irgendetwas gewesen sein".

Nun versuchen wir den zweitletzten Pinselstrich rückgängig machen. Dazu suchen wir nun nach einer Zeile oder Spalte, die nur aus Nullen und einer einzigen Farbe besteht. Finden wir keine solche Linie ist es ein Fake, sonst ersetzen wir die Linie wieder durch Fragezeichen. Dies wiederholen wir nun so lange, bis wir irgendwo stecken bleiben, oder nur noch Fragezeichen übrig sind. Ist letzteres der Fall, so ist das Bild echt.

Speicher O(m*n)
Laufzeit O(m*n + (m+n)*k)