第四回オフラインリアルタイムどう書くの参考問題の解答

第四回オフラインリアルタイムどう書くの参考問題 (http://qiita.com/items/9c514267214d3917edf2)
をJavaで解きました。

単純な数え上げで、所要時間は3時間程度。

CountRoute.java

import java.util.List;
import java.util.ArrayList;

public class CountRoute {

    private final List<List<Point>> closed;
    private final Point start;
    private final Point goal;

    public CountRoute(String closedData) {
        closed = parseClosedEdge(closedData);
        start = Point.getInstance(0, 0);
        goal = Point.getInstance(Point.SIZE-1, Point.SIZE-1);
    }

    private List<List<Point>> parseClosedEdge(String closedData) {
        List<List<Point>> ret = new ArrayList<List<Point>>();
        for ( String closedEdge : closedData.split(" ") ) {
            List<Point> list = new ArrayList<Point>();
            for ( char c : closedEdge.toCharArray() ) {
                int index = c - 'a';
                list.add(Point.getInstance(index/Point.SIZE, index%Point.SIZE));
            }
            ret.add(list);
        }
        return ret;
    }

    private boolean isClosedEdge(Point prev, Point p) {
        if ( closed == null ) {
            return false;
        }
        for ( List<Point> list : closed ) {
            if ( list.contains(prev) && list.contains(p) ) {
                return true;
            }
        }
        return false;
    }

    public int count() {
        List<Point> passed = new ArrayList<Point>();
        return move(null, start, passed);
    }

    private int move(Point prev, Point p, List<Point> passed) {
        if ( p == null || passed.contains(p) || isClosedEdge(prev, p) ) {
            return 0;
        }
        if ( goal.equals(p) ) {
            return 1;
        }
        int num = 0;
        passed.add(p);
        num += move( p, p.up(), passed );
        num += move( p, p.left(), passed );
        num += move( p, p.right(), passed );
        num += move( p, p.down(), passed );
        passed.remove(p);
        return num;
    }

    public static void main(String[] args) {
        for ( String[] test : testData ) {
            int result = new CountRoute(test[0]).count();
            System.out.println( test[0] );
            if ( result != Integer.parseInt(test[1]) ) {
                System.out.println( "***Error*** " + test[1] + "->" );
            }
            System.out.println( result );
        }
    }
    
    private static final String testData[][] = {
        { "", "8512", },
        { "af", "4256", },
        { "xy", "4256", },
        { "pq qr rs st di in ns sx", "184", },
        { "af pq qr rs st di in ns sx", "92", },
        { "bg ch di ij no st", "185", },
        { "bc af ch di no kp mr ns ot pu rs", "16", },
        { "ab af", "0", },
        { "ty xy", "0", },
        { "bg ch ej gh lm lq mr ot rs sx", "11", },
        { "ty ch hi mn kp mr rs sx", "18", },
        { "xy ch hi mn kp mr rs sx", "32", },
        { "ch hi mn kp mr rs sx", "50", },
        { "ab cd uv wx", "621", },
        { "gh mn st lq qr", "685", },
        { "fg gl lm mr rs", "171", },
    };
}

Point.java

class Point {
    public static final int SIZE = 5;

    private final int x;
    private final int y;
    private Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public static Point getInstance(int x, int y) {
        if ( x < 0 || x >= SIZE || y < 0 || y >= SIZE ) {
            return null;
        }
        return new Point(x, y);
    }

    public Point up() { return getInstance(x, y-1); }
    public Point left() { return getInstance(x-1, y); }
    public Point right() { return getInstance(x+1, y); }
    public Point down() { return getInstance(x, y+1); }

    @Override public boolean equals(Object o) {
        if ( !(o instanceof Point) ) {
            return false;
        }
        Point p = (Point)o;
        return this.x == p.x && this.y == p.y;
    }
    @Override public int hashCode() {
        int result = 17;
        result = result*31 + x;
        result = result*31 + y;
        return result;
    }

    @Override public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Point: x = ");
        sb.append(x);
        sb.append(", y = ");
        sb.append(y);
        return sb.toString();
    }
}