GCJ2015-D-small

gistfile1.java

package gcj2015;

import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class D {

    private static final String gabriel = "GABRIEL";
    private static final String richard = "RICHARD";

    public static class Omino {
        public final String[] blocks;
        private final int id;

        public Omino(int i, String[] blocks) {
            this.id = i;
            this.blocks = blocks;
        }

        public int getWidth() {
            return blocks[0].length();
        }

        public int getHeight() {
            return blocks.length;
        }

        public boolean hasUnit(int x, int y) {
            return blocks[y].charAt(x) == '1';
        }

        public int getId() {
            return id;
        }
    }

    public static class Grid {
        private final int r;
        private final int c;
        private final boolean[] body;

        public Grid(int r, int c) {
            this.r = r;
            this.c = c;
            this.body = new boolean[r*c];
        }

        public void put(Omino o, int pos) {
            int x = pos % c;
            int y = pos / c;
            for(int i = 0; i < o.getHeight(); i++) {
                for (int j = 0; j < o.getWidth(); j++) {
                    int current = (x + j) + (y + i) * c;
                    if(o.hasUnit(j,i)) {
                        body[current] = true;
                    }
                }
            }
        }

        public boolean canPut(Omino o, int pos) {
            int x = pos % c;
            int y = pos / c;

            if (o.getWidth() + x > c) {
                return false;
            }
            if (o.getHeight() + y > r) {
                return false;
            }

            for(int i = 0; i < o.getHeight(); i++) {
                for (int j = 0; j < o.getWidth(); j++) {
                    int current = (x + j) + (y + i) * c;
                    if(o.hasUnit(j,i)) {
                        if(body[current]) return false;
                    }
                }
            }
            return true;
        }

        private void remove(Omino o, int pos) {
            int x = pos % c;
            int y = pos / c;

            for(int i = 0; i < o.getHeight(); i++) {
                for (int j = 0; j < o.getWidth(); j++) {
                    int current = (x + j) + (y + i) * c;
                    if(o.hasUnit(j,i)) {
                        body[current] = false;
                    }
                }
            }
        }

        public boolean isFill() {
            for (boolean aBody : body) {
                if (!aBody) return false;
            }
            return true;
        }

        public boolean tryFill2(List<Omino> ominos, int pos) {
            if (pos >= body.length) return false;

            for (Omino o : ominos) {
                if (canPut(o, pos)) {
                    put(o, pos);
                    if (isFill()) return true;

                    if (tryFill2(ominos, pos + 1)) {
                        return true;
                    }
                    remove(o, pos);
                }
            }

            return tryFill2(ominos, pos + 1);
        }

        public boolean tryFill(List<Omino> choosedList, List<Omino> all) {
            for(int pos  = 0; pos < body.length; pos++) {
                for (Omino o : choosedList) {
                    if (canPut(o, pos)) {
                        put(o, pos);
                        if (isFill()) return true;

                        if (tryFill2(all, 0)) {
                            return true;
                        }
                        remove(o, pos);
                    }
                }
            }
            return false;
        }
    }

    public static String run(int x, int r, int c) {
        List<List<Omino>> xOminoList = getXOminoList(x);
        List<Omino> flattenList = new ArrayList<>();
        for(List<Omino> lo: xOminoList) {
            flattenList.addAll(lo);
        }

        for(List<Omino> lo: xOminoList) {
            Grid grid = new Grid(r, c);
            if (!(grid.tryFill(lo, flattenList))) {
                return richard;
            }
        }
        return gabriel;
    }

    static final List<List<Omino>> ominos1;
    static final List<List<Omino>> ominos2;
    static final List<List<Omino>> ominos3;
    static final List<List<Omino>> ominos4;

    static {
        //1-OMINO
        ominos1 = new ArrayList<>();
        List<Omino> lo1 = new ArrayList<>();
        lo1.add(new Omino(1, new String[]{
                "1"
        }));
        ominos1.add(lo1);

        //2-OMINO
        ominos2 = new ArrayList<>();
        List<Omino> lo2 = new ArrayList<>();
        lo2.add(new Omino(1, new String[]{
                "11"
        }));
        lo2.add(new Omino(1, new String[]{
                "1",
                "1"
        }));
        ominos2.add(lo2);

        //3-OMINO
        ominos3 = new ArrayList<>();
        List<Omino> lo3_1 = new ArrayList<>();
        lo3_1.add(new Omino(1, new String[]{
                "111"
        }));
        lo3_1.add(new Omino(1, new String[]{
                "1",
                "1",
                "1"
        }));
        ominos3.add(lo3_1);

        List<Omino> lo3_2 = new ArrayList<>();
        lo3_2.add(new Omino(2, new String[]{
                "10",
                "11"
        }));
        lo3_2.add(new Omino(2, new String[]{
                "01",
                "11"
        }));
        lo3_2.add(new Omino(2, new String[]{
                "11",
                "01"
        }));
        lo3_2.add(new Omino(2, new String[]{
                "11",
                "10"
        }));
        ominos3.add(lo3_2);

        //4-OMINOS
        ominos4 = new ArrayList<>();
        List<Omino> lo4_1 = new ArrayList<>();
        lo4_1.add(new Omino(1, new String[]{
                "1111"
        }));
        lo4_1.add(new Omino(1, new String[]{
                "1",
                "1",
                "1",
                "1"
        }));
        ominos4.add(lo4_1);
        List<Omino> lo4_2 = new ArrayList<>();
        lo4_2.add(new Omino(2, new String[]{
                "11",
                "11"
        }));
        ominos4.add(lo4_2);

        List<Omino> lo4_3 = new ArrayList<>();
        lo4_3.add(new Omino(3, new String[]{
                "111",
                "010"
        }));
        lo4_3.add(new Omino(3, new String[]{
                "10",
                "11",
                "10"
        }));
        lo4_3.add(new Omino(3, new String[]{
                "010",
                "111"
        }));
        lo4_3.add(new Omino(3, new String[]{
                "01",
                "11",
                "01"
        }));
        ominos4.add(lo4_3);

        List<Omino> lo4_4 = new ArrayList<>();
        lo4_4.add(new Omino(4, new String[]{
                "10",
                "10",
                "11"
        }));
        lo4_4.add(new Omino(4, new String[]{
                "01",
                "01",
                "11"
        }));
        lo4_4.add(new Omino(4, new String[]{
                "11",
                "10",
                "10"
        }));
        lo4_4.add(new Omino(4, new String[]{
                "11",
                "01",
                "01"
        }));
        lo4_4.add(new Omino(4, new String[]{
                "100",
                "111"
        }));
        lo4_4.add(new Omino(4, new String[]{
                "001",
                "111"
        }));
        lo4_4.add(new Omino(4, new String[]{
                "111",
                "100"
        }));
        lo4_4.add(new Omino(4, new String[]{
                "111",
                "001"
        }));
        ominos4.add(lo4_4);

        List<Omino> lo4_5 = new ArrayList<>();
        lo4_5.add(new Omino(5, new String[]{
                "110",
                "011"
        }));
        lo4_5.add(new Omino(5, new String[]{
                "011",
                "110"
        }));
        lo4_5.add(new Omino(5, new String[]{
                "01",
                "11",
                "10"
        }));
        lo4_5.add(new Omino(5, new String[]{
                "10",
                "11",
                "01"
        }));
        ominos4.add(lo4_5);
    }

    public static List<List<Omino>> getXOminoList(int x) {
        if (x == 1) {
            return ominos1;
        }
        if (x == 2) {
            return ominos2;
        }
        if (x == 3) {
            return ominos3;
        }
        if (x == 4) {
            return ominos4;
        }

        //FIXME
        return new ArrayList<>();
    }

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(new FileReader(args[0]));
        FileWriter writer = new FileWriter(args[1]);
        int t = scanner.nextInt();
        for(int i = 1; i <= t; i++) {
            int x = scanner.nextInt();
            int r = scanner.nextInt();
            int c = scanner.nextInt();

            String resultOutput = String.format("Case #%d: %s", i, run(x,r,c));
            System.out.println(resultOutput);
            writer.append(resultOutput);
            writer.append("\n");
        }
        writer.close();
    }
}