試験問題やった

http://okajima.air-nifty.com/b/2010/01/post-abc6.html
いまさら目にしてなんとなくやってみた。
使用言語Java、所要時間１時間ほど。遊びました、細部は適当、コード長め。

• ありうる選択肢を状態としてもつ（ゴールに到達可能な迷路なら常にひとつ以上の状態が存在）
• 1ターンで、各状態を1マスだけすすめる。選択肢が複数あれば状態が増える
• いずれかの状態が一度でも通ったルートは保存しておき、過去に別の状態が通過済であるポイントに来た状態は、死ぬ

package map;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class Maze {

    public static void main(String[] args) throws IOException {

        Maze maze = new Maze(Maze.class.getResourceAsStream("/map/map1.txt"));
        System.out.println(maze);

        List<Transition> transitions = new ArrayList<Transition>();
        transitions.add(maze.start());

        LOOP: while (true) {
            List<Transition> nexts = new ArrayList<Transition>();
            if (transitions.isEmpty()) {
                System.err.println("ムリ！！！");
                System.exit(-1);
            }
            for (Transition t : transitions) {
                nexts.addAll(t.next());
            }
            for (Transition next : nexts) {
                if (next.isGoal()) {
                    System.out.println(next);
                    break LOOP;
                }
            }
            transitions = nexts;
        }
    }

    private char[][] map;
    private Point start;
    private Point goal;

    private Set<Point> passedPoints = new HashSet<Point>();

    public Maze(InputStream in) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        List<char[]> lines = new ArrayList<char[]>();
        String line = null;
        while ((line = reader.readLine()) != null) {
            lines.add(line.toCharArray());
        }
        map = new char[lines.size()][];
        for (int i = 0; i < lines.size(); i++) {
            map[i] = lines.get(i);
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 'S') {
                    start = new Point(j, i);
                } else if (map[i][j] == 'G') {
                    goal = new Point(j, i);
                }
            }
        }
    }

    public boolean savePassedPoint(Point point) {
        return passedPoints.add(point);
    }

    public boolean isWay(Point p) {
        return p.x > 0 && p.x < map[0].length && p.y > 0 && p.y < map.length
                && map[p.y][p.x] != '*';
    }

    public List<Point> getNext(Point point) {
        List<Point> nexts = new ArrayList<Point>(4);
        for (Point p : point.getFourWays()) {
            if (isWay(p)) {
                nexts.add(p);
            }
        }
        return nexts;
    }

    public Transition start() {
        return new Transition();
    }

    @Override
    public String toString() {
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < map.length; i++) {
            buf.append(map[i]).append("\n");
        }
        return new String(buf);
    }

    public class Transition {

        private Point current;
        private List<Point> route = new ArrayList<Point>();

        Transition() {
            this.current = start;
        }

        public List<Transition> next() {
            List<Point> nexts = getNext(current);
            for (Iterator<Point> itr = nexts.iterator(); itr.hasNext();) {
                if (!savePassedPoint(itr.next())) {
                    itr.remove();
                }
            }
            List<Transition> transitions = new ArrayList<Transition>();
            for (Point next : nexts) {
                Transition t = dup();
                t.current = next;
                t.route.add(next);
                transitions.add(t);
            }
            return transitions;
        }

        public boolean isGoal() {
            return current.equals(goal);
        }

        public Transition dup() {
            Transition t = new Transition();
            t.current = this.current;
            t.route = new ArrayList<Point>(this.route);
            return t;
        }

        @Override
        public String toString() {
            StringBuilder buf = new StringBuilder();
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[i].length; j++) {
                    Point p = new Point(j, i);
                    if (p.equals(goal)) {
                        buf.append('G');
                    } else if (route.contains(p)) {
                        buf.append('$');
                    } else {
                        buf.append(map[i][j]);
                    }
                }
                buf.append('\n');
            }
            return new String(buf);
        }

    }

    public static class Point {

        public int x;
        public int y;

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

        public Point[] getFourWays() {
            return new Point[] { new Point(x, y - 1), new Point(x, y + 1),
                    new Point(x - 1, y), new Point(x + 1, y) };
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Point)) {
                return false;
            }
            Point other = (Point) obj;
            return this.x == other.x && this.y == other.y;
        }

        @Override
        public int hashCode() {
            int hash = this.x;
            hash ^= this.y << 7;
            return hash;
        }
    }

}