おねえさんのコンピュータ(幅優先 in Java)

.gitignore

*~
*.class

letcount.java

import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
import java.math.BigInteger;

public class letcount {
    public static void main(String[] args) {
        Graph graph = Graph.makeGrid(10, 10);
        int[] mate = new int[graph.countNodes + 1];
        HashMap<FrontierMate, BigInteger> map = new HashMap<FrontierMate, BigInteger>();
        map.put(FrontierMate.getRoot(), BigInteger.ONE);

        for(int i = 0; i < graph.edges.length; ++i) {
            HashMap<FrontierMate, BigInteger> new_map = new HashMap<FrontierMate, BigInteger>();
            Edge edge = graph.edges[i];
            for(Map.Entry<FrontierMate, BigInteger> e : map.entrySet()) {
                FrontierMate old_mate = e.getKey();
                BigInteger val = e.getValue();
                FrontierMate new_mate;

                old_mate.toMate(graph, mate);
                new_mate = FrontierMate.getFrontier(i, graph, mate);
                if(new_mate != null) {
                    if(new_map.containsKey(new_mate)) {
                        new_map.put(new_mate, new_map.get(new_mate).add(val));
                    } else {
                        new_map.put(new_mate, val);
                    }
                }

                int a = edge.from, b = edge.to;
                int c = mate[a], d = mate[b];
                mate[a] = 0;
                mate[b] = 0;
                mate[c] = d;
                mate[d] = c;
                new_mate = FrontierMate.getFrontier(i, graph, mate);
                if(c != 0 && d != 0 && a != d && b != c && new_mate != null) {
                    if(new_map.containsKey(new_mate)) {
                        new_map.put(new_mate, new_map.get(new_mate).add(val));
                    } else {
                        new_map.put(new_mate, val);
                    }
                }
            }
            map = new_map;
            //System.out.println();
        }

        BigInteger result = BigInteger.ZERO;
        for(Map.Entry<FrontierMate, BigInteger> e : map.entrySet()) {
            result = e.getValue().add(result);
        }
        System.out.println(result);
        return ;
    }
}

class FrontierMate {
    private int no;
    private int[] frontmate;

    private FrontierMate(int edge_no, Graph g, int[] mate) {
        no = edge_no;
        int[] frontiers = g.frontiers[edge_no];
        frontmate = new int[frontiers.length];
        for(int i = 0; i < frontiers.length; ++i) {
            frontmate[i] = mate[frontiers[i]];
        }
    }

    private FrontierMate(int edge_no, int[] frontmate) {
        this.no = edge_no;
        this.frontmate = frontmate;
    }

    public static FrontierMate getFrontier(int edge_no, Graph g, int[] mate) {
        for(int i : g.frontiers[edge_no]) {
            if(i==1 || mate[i] == 0 || mate[i] == 1 || mate[i] == i) continue;
            if(Arrays.binarySearch(g.frontiers[edge_no+1], i) < 0) {
                return null;
            }
        }
        FrontierMate fm = new FrontierMate(edge_no + 1, g, mate);
        if(!fm.isConnected(1)) return null;
        return fm;
    }

    public static FrontierMate getRoot() {
        return new FrontierMate(0, new int[0]);
    }

    public int[] toMate(Graph g, int[] mate) {
        int[] frontiers = g.frontiers[no];
        for(int i = 0; i < mate.length; ++i) {
            mate[i] = i;
        }
        for(int i = 0; i < frontiers.length; ++i) {
            mate[frontiers[i]] = frontmate[i];
        }
        return mate;
    }

    public int hashCode() {
        int code = no;
        for(int i : frontmate) {
            code = code * 2 + i;
            if(code < 0) {
                code ^= 0x31415926;
            }
        }
        return code;
    }

    public boolean equals(Object obj) {
        if(obj instanceof FrontierMate) {
            FrontierMate m = (FrontierMate)obj;
            if(no != m.no) return false;
            if(frontmate.length != m.frontmate.length) return false;
            for(int i = 0; i < frontmate.length; ++i) {
                if(frontmate[i] != m.frontmate[i]) return false;
            }
            return true;
        }
        return false;
    }

    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("(");
        builder.append(no);
        builder.append(", [");
        for(int i : frontmate) {
            builder.append(i);
            builder.append(", ");
        }
        builder.append("])");
        return builder.toString();
    }

    public boolean isConnected(int no) {
        for(int i : frontmate) {
            if(i == no) return true;
        }
        return false;
    }
}

class Edge {
    int from, to;

    public Edge(int from, int to) {
        this.from = from;
        this.to = to;
    }

    public String toString() {
        return "(" + from + ", " + to + ")";
    }
}

class Graph {
    public Edge[] edges;
    public int countNodes;
    public int[][] frontiers;

    private Graph(Edge[] edges) {
        this.edges = edges;
        int max = 1;
        for(Edge e : edges) {
            if(e.from > max) max = e.from;
            if(e.to > max) max = e.to;
        }
        countNodes = max;

        int[] count = new int[max + 1];
        for(Edge e : edges) {
            ++count[e.from];
            ++count[e.to];
        }

        frontiers = new int[edges.length + 1][];
        int[] reached = new int[max + 1];
        for(int i = 0; i < edges.length; ++i) {
            java.util.ArrayList<Integer> list = new java.util.ArrayList<Integer>();
            for(int j = 1; j <= max; ++j) {
                if(reached[j] == 0) continue;
                if(reached[j] == count[j]) continue;
                list.add(j);
            }
            frontiers[i] = new int[list.size()];
            for(int j = 0; j < list.size(); ++j) {
                frontiers[i][j] = list.get(j);
            }
            ++reached[edges[i].from];
            ++reached[edges[i].to];
        }
        frontiers[edges.length] = new int[1];
        frontiers[edges.length][0] = max;
    }

    public static Graph makeGrid(int width, int height) {
        java.util.ArrayList<Edge> list = new java.util.ArrayList<Edge>();
        int[][] nodes = new int[height+1][width+1];

        for(int y = 0; y <= height; ++y) {
            for(int x = 0; x <= width; ++x) {
                nodes[y][x] = 1 + x + y * (width+1);
            }
        }

        for(int y = 0; y < height; ++y) {
            for(int x = 0; x < width; ++x) {
                list.add(new Edge(nodes[y][x], nodes[y][x+1]));
                list.add(new Edge(nodes[y][x], nodes[y+1][x]));
            }
            list.add(new Edge(nodes[y][width], nodes[y+1][width]));
        }
        for(int x = 0; x < width; ++x) {
            list.add(new Edge(nodes[height][x], nodes[height][x+1]));
        }

        Edge[] edges = new Edge[list.size()];
        list.toArray(edges);
        return new Graph(edges);
    }
}