import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import javax.imageio.ImageIO;

public class UnobstructedRectangles {

    public class Rectangle {

        public Color colour;
        public int zIndex;
        public Point topLeft;
        public Point topRight;
        public Point bottomLeft;
        public Point bottomRight;

        public Rectangle() {
            colour = new Color(255, 255, 255);
        }
    }

    private BufferedImage image;
    private List<Rectangle> rectangles;

    public static void main(String[] args) throws IOException {
        new UnobstructedRectangles();
    }

    public UnobstructedRectangles() throws IOException {
        rectangles = new ArrayList<Rectangle>();
        mapRectangles();
        traceRectangles();
        drawSolution();
    }

    public void mapRectangles() throws IOException {
        image = ImageIO.read(new File("input.png"));

        for (int y = 0; y < image.getHeight(); y++) {
            for (int x = 0; x < image.getWidth(); x++) {
                Color c = new Color(image.getRGB(x, y));

                if (c.getRGB() == -1) {
                    continue;
                }

                Rectangle rect = null;
                for (Rectangle re : rectangles) {
                    if (re.colour.equals(c)) {
                        rect = re;
                        break;
                    }
                }

                if (rect == null) {
                    rect = new Rectangle();
                    rectangles.add(rect);
                }

                if (rect.topLeft == null) {
                    rect.topLeft = new Point(x, y);
                    rect.topRight = new Point(x, y);
                    rect.bottomLeft = new Point(x, y);
                    rect.bottomRight = new Point(x, y);
                    rect.colour = new Color(c.getRGB());
                }

                if (x < rect.topLeft.x) {
                    rect.topLeft.x = x;
                    rect.bottomLeft.x = x;
                }

                if (x > rect.topRight.x) {
                    rect.topRight.x = x;
                    rect.bottomRight.x = x;
                }

                rect.bottomLeft.y = y;
                rect.bottomRight.y = y;
            }
        }
    }

    public void traceRectangles() {

        List<Color> invadingColours = null;
        for (Rectangle r : rectangles) {
            invadingColours = new ArrayList<Color>();
            for (int y = r.topLeft.y; y <= r.bottomLeft.y; y++) {
                for (int x = r.topLeft.x; x <= r.topRight.x; x++) {
                    if (image.getRGB(x, y) != r.colour.getRGB()) {

                        Color overlappingColour = new Color(image.getRGB(x, y));
                        boolean found = false;
                        for (Color invCol : invadingColours) {
                            if (invCol.equals(overlappingColour)) {
                                found = true;
                                break;
                            }
                        }
                        if (!found) {
                            invadingColours.add(overlappingColour);
                        } else {
                            continue;
                        }

                        Rectangle overlappingRectangle = null;
                        for (Rectangle re : rectangles) {
                            if (re.colour.equals(overlappingColour)) {
                                overlappingRectangle = re;
                                break;
                            }
                        }

                        if (overlappingRectangle != null) {
                            overlappingRectangle.zIndex = r.zIndex + 1;
                        }
                    }
                }
            }

        }
    }

    public void drawSolution() throws IOException {

        Collections.sort(rectangles, new RectangleZIndexComparator());
        for (int ii = rectangles.size(); ii > 0; ii--) {
            drawRectangles(rectangles.subList(0, ii), rectangles.size() - ii + 1);
        }
    }

    public void drawRectangles(List<Rectangle> rects, int ii) throws IOException {

        BufferedImage outputImage = new BufferedImage(image.getWidth(), image.getHeight(), BufferedImage.TYPE_INT_ARGB);
        Graphics2D g = (Graphics2D) outputImage.getGraphics();

        for (Rectangle r : rects) {

            g.setColor(r.colour);

            int x = r.topLeft.x;
            int y = r.topLeft.y;
            int width = r.topRight.x - r.topLeft.x;
            int height = r.bottomLeft.y - r.topLeft.y;

            g.fillRect(x, y, width, height);
        }

        ImageIO.write(outputImage, "png", new File("output_" + ii + ".png"));
    }

    private void log() {
        StringBuilder sb = new StringBuilder();

        for (Rectangle r : rectangles) {
            sb.append("[");
            sb.append(String.format("%03d", r.colour.getRed()));
            sb.append(",");
            sb.append(String.format("%03d", r.colour.getGreen()));
            sb.append(",");
            sb.append(String.format("%03d", r.colour.getBlue()));
            sb.append(String.format("]\tZ-index: %d", r.zIndex));
            sb.append("\tTop left: ");
            sb.append(r.topLeft.x);
            sb.append(",");
            sb.append(r.topLeft.y);
            sb.append(";\tTop right: ");
            sb.append(r.topRight.x);
            sb.append(",");
            sb.append(r.topRight.y);
            sb.append(";\tBottom left: ");
            sb.append(r.bottomLeft.x);
            sb.append(",");
            sb.append(r.bottomLeft.y);
            sb.append(";\tBottom right: ");
            sb.append(r.bottomRight.x);
            sb.append(",");
            sb.append(r.bottomRight.y);
            System.out.println(sb.toString());
            sb.setLength(0);
        }
    }

    public class RectangleZIndexComparator implements Comparator<Rectangle> {

        @Override
        public int compare(Rectangle r1, Rectangle r2) {
            return r1.zIndex > r2.zIndex ? 1 : (r1.zIndex == r2.zIndex ? 0 : -1);
        }
    }

}