Ten obraz powstał przez nałożenie na siebie 7 prostokątów o różnych kolorach:

Czarne i bordowe prostokąty nie są zasłonięte , to znaczy, żadne inne prostokąty nie są nad nimi.

Napisz program, który pobiera obraz taki jak ten, i usuń pojedynczy niezablokowany prostokąt, wysyłając obraz wynikowy.

Przykład

Jeśli uruchomiłeś program na powyższym obrazku i nadal uruchamiałeś go ponownie na wyjściu, może to wyglądać następująco.

Run 1 - Czarny usunięty (mógł być bordowy):

Run 2 - Maroon usunięty (tylko wybór):

Przebieg 3 - Żółty usunięty (tylko wybór):

Uruchom 4 - niebieski usunięty (mógł być zielony):

Uruchom 5 - Usunięto kolor zielony (tylko wybór):

Run 6 - Brązowy usunięty (tylko wybór):

Uruchom 7 - Usunięto czerwony (tylko wybór):

Wszelkie dodatkowe przebiegi powinny dawać ten sam biały obraz.

^{Mam nadzieję, że Stack Exchange nie skompresował żadnego z tych obrazów.}

Obraz zawsze będzie miał białe tło, a każdy prostokąt będzie miał unikalny kolor RGB, który nie jest biały.

Możesz założyć, że obraz zawsze może być interpretowany jako zestaw nakładających się prostokątów. W szczególności można założyć, że w przypadku określonego koloru piksel o tym kolorze najbliższym górnej krawędzi obrazu jest częścią górnej krawędzi prostokąta tego koloru. To samo dotyczy dolnej, lewej i prawej krawędzi.

Na przykład na tym obrazie górna krawędź czerwonego prostokąta znajdowałaby się tuż poniżej dolnej krawędzi żółtego prostokąta, ponieważ pomarańczowy prostokąt zakrywał starą czerwoną górną krawędź:

Na tym obrazku czerwony prostokąt można najpierw usunąć (wraz z czarnym / bordowym / pomarańczowym / szarym):

Gdy kolejność dolnych prostokątów jest niejednoznaczna, możesz nadać im dowolną kolejność.

Na przykład lewy obraz tutaj może stać się środkiem lub prawą stroną:

Wyjście nie powinno mieć paradoksalnych nakładek (więc powinno być możliwe zrobienie tego za pomocą algorytmu malarza ). Na tym obrazku ( dzięki user23013 ) musiałby być zielony pod pomarańczowym prostokątem:

Dodatkowe Szczegóły

• Obraz i prostokąty mogą mieć dowolne wymiary.
• Prostokąty mogą dotykać ramki obrazu.
• Może być do 256 prostokątów ³ - 1.
• Jeśli wejście jest całkowicie białe, wyjście powinno również być.
• Możesz użyć bibliotek obrazów.
• Dane wejściowe powinny być nazwą pliku obrazu lub surowymi danymi obrazu. Może pochodzić ze standardowego wejścia lub wiersza poleceń.
• Dane wyjściowe można zapisać do tego samego lub innego pliku obrazu, wyrzucać na surowo do standardowego wyjścia lub po prostu wyświetlać.
• Dowolny typowy bezstratny format pliku obrazu truecolor jest dozwolony.

Zgłoszenie z najmniejszą liczbą bajtów wygrywa.

CJam, 241 bajtów

(z usuniętymi znakami nowej linii).

rri:Hri:Vri:Q[q~]3/_Qa3*a+_|$W%:Pf{\a#}:AH/:B0ff*
P,,[AHAW%HBz:+_W%V\V]2/
ff{~@@f=/::|1#}0Ua4*t:R;
P0f<
V{H{BI=J=_2$=
0R{"I>! I+V<J>! J+H<"4/+4/z{~~}%:&1$*\)}%);2$-|t
}fJ}fI
[P,{_La#\1$0t1$f-}*;;]
{:TR=2/~\~V\-,>\f{\_3$=@~H\-,>{Tt}/t}~}/
:~Pf=:~
~]S*N

Używa formatu pliku ppm. Przykładowe użycie (przy użyciu ImageMagick):

convert IVYvE.png -compress none ppm:-| (time /path/to/cjam-0.6.4.jar 1.cjam) |display

Cóż, jest za długi i za wolny ... Działa na przykład około minuty.

Zmieniłem rozmiar przypadków testowych (i dodałem kilka innych), aby ułatwić testowanie.

Wygląda na to, że informacje o przestrzeni kolorów zostały utracone, więc kolory są nieco inne.

Python, 690 651 610 606 594 569 bajtów

Skrypt odczytuje nazwę obrazu ze standardowego wejścia.

Wykrywa krawędzie każdego prostokąta, sortuje je według liczby różnych kolorów, które zawierają (niezablokowane prostokąty zawierają tylko 1 kolor, a następnie pojawiają się na końcu listy)

Ta lista służy do przerysowania obrazu. Kolejność przerysowywania jest ustalana przez wybranie permutacji listy, która generowałaby obraz wyjściowy, który miałby najmniejszą różnicę pikseli w danych wejściowych.

z importu PIL Obraz jako l, ImageDraw jako D; z itertools import *; O, R, I, Z, k = [], range, l.open (raw_input ()), {}, lambda x: -x [1 ]; (W, H), Q = I.size, I.load ()
dla i, jw produkcie (R (W), R (H)):
 c = Q [i, j]
 jeśli cw Z: x, y, X, Y = Z [c]; Z [c] = [x, y, max (X, i), max (Y, j)]
 else: Z [c] = [i, j, 0,0]
dla nw permutacjach (posortowane ([(c, len ({Q [g] dla gw produkcie (R (x, X), R (y, Y))))) dla c, (x, y, X, Y) w Z.items ()], key = k) [1: -1]): o = l. Nowa (I.mode, I.size, 0xFFFFFF); [D.Draw (o). Prostokąt (Z [c], fill = c) dla c, _ in n]; O + = [(o, suma (abs (ab) dla t, T w zip (I.getdata (), o.getdata ()) dla a, b zip (t, T)))]
max (O, key = k) [0] .show ()

Java - 1483 bajtów

Nie jestem świetnym golfistą, niech to będzie jasne; więc gadatliwość nie jest całkowicie winą Javy ;-) Niemniej jednak wydawało się, że to naprawdę zabawne wyzwanie. Rozwiązałem to w sposób, który - myślę - jest trochę nudny i gadatliwy, ale hej. Działa, jest (względnie) szybki, a zwłaszcza fajnie!

Pomysł jest następujący: Sprawdź każdy piksel, zaczynając od lewego górnego rogu, aż do prawego dolnego rogu. Czy to biały piksel? Ignorować. Czy to jest kolorowe? Fajnie, śledźmy go i spróbujmy określić jego granice (lewy górny, prawy górny, lewy dolny, prawy dolny).

Po zakończeniu sprawdź obszar każdego prostokąta. Czy zawiera inny kolor niż kolor prostokąta? Następnie dowiedz się, jaki prostokąt należy do tego koloru i zaktualizuj indeks Z pokrywającego się z nim o 1.

Na koniec narysuj wszystkie prostokąty, biorąc pod uwagę wskaźniki Z. Działa właściwie jak indeks Z znany z CSS i innych materiałów 3D. Prostokąty o najniższym indeksie Z są rysowane jako pierwsze, a najwyższe - indeks Z na końcu.

import java.awt.*;import java.awt.image.*;import java.io.File;import java.util.*;import java.util.List;import javax.imageio.*;class A{class R{public Color k=new Color(-1);public int z;public Point a;public Point b;public Point c;public Point d;}public static void main(String[]w)throws Exception{BufferedImage i=ImageIO.read(new File(w[0]));List<R>r=new Vector<R>();for(int y=0;y<i.getHeight();y++){for(int x=0;x<i.getWidth();x++){Color c=new Color(i.getRGB(x,y));if(c.getRGB()==-1){continue;}R t=null;for(R s:r){if(s.k.equals(c)){t=s;}}if(t==null){t=new A().new R();r.add(t);}if(t.a==null){t.a=new Point(x, y);t.b=new Point(x, y);t.c=new Point(x, y);t.d=new Point(x, y);t.k=new Color(c.getRGB());}if(x<t.a.x){t.a.x=x;t.c.x=x;}if(x>t.b.x){t.b.x=x;t.d.x=x;}t.c.y=y;t.d.y=y;}}for(R s:r){List<Color>b=new Vector<Color>();for(int y=s.a.y;y<=s.c.y;y++){for(int x = s.a.x;x<=s.b.x;x++){if(i.getRGB(x, y)!=s.k.getRGB()){Color a=new Color(i.getRGB(x,y));boolean q=false;for(Color l:b){if(l.equals(a)){q=true;}}if(!q){b.add(a);} else {continue;}R f=null;for(R k:r){if(k.k.equals(a)){f=k;}}f.z=s.z+1;}}}}Collections.sort(r,new Comparator<R>(){public int compare(R a, R b){return a.z>b.z?1:(a.z==b.z?0:-1);}});for(int ii=r.size();ii>0;ii--){BufferedImage d=new BufferedImage(i.getWidth(),i.getHeight(),2);Graphics2D g=(Graphics2D)d.getGraphics();for(R s : r.subList(0, ii)){g.setColor(s.k);g.fillRect(s.a.x,s.a.y,s.b.x-s.a.x,s.c.y-s.a.y);}ImageIO.write(d,"png",new File(r.size()-ii+".png"));}}}

Pełny kod, który jest nieco - i to mało powiedziane ;-) - napisany jaśniej, można znaleźć tutaj: http://pastebin.com/UjxUUXRp

Teraz, gdy widzę poddanie się dietera, mogłem ułatwić niektóre części. Naprawdę nie jest konieczne znalezienie prostokąta, którego kolor nachodzi na inny prostokąt. Mógłbym po prostu policzyć liczbę kolorów „inwazji”.