import java.util.Iterator;
import java.util.LinkedHashSet;

public class MazeSolver {

    private Maze maze;
    private Coordinate start;

    private LinkedHashSet<Coordinate> route;
    private boolean solvable = false;
    private Coordinate currPos;
    private boolean done = false;

    private static final int[] DIRECTIONS = {-2, -1, 2, 1};

    public MazeSolver(Maze maze, Coordinate start) {
        if (!maze.isPassable(start) || maze.isOffLimits(start)) {
            throw new IllegalArgumentException("Invalid starting point: " + start);
        }

        this.maze = maze;
        this.start = start;
        this.route = new LinkedHashSet<Coordinate>();
    }

    public void solve() {
        route.add(start);

        currPos = start;
        int lastDirIdx = 1;

        while (!done) {
            boolean moved = false;
            // always try to keep a wall on the left hand side
            // lastDirIdx - 1 is the index for the direction to turn left from current facing
            for (int i = -1; i < DIRECTIONS.length - 1; i++) {
                // + 4 to stay positive.
                int dirIdx = (lastDirIdx + i + 4) % DIRECTIONS.length;
                //System.out.println(lastDirIdx + "/" + DIRECTIONS[lastDirIdx] + ", " + dirIdx + "/" + DIRECTIONS[dirIdx]);
                if (tryNext(currPos.move(DIRECTIONS[dirIdx]))) {
                    lastDirIdx = dirIdx;
                    moved = true;
                    break;
                }
            }

            // this deals with the special case of an isolated starting point.
            if (!moved) {
                done = true;
            }
        }
    }

    private boolean tryNext(Coordinate next) {
        System.out.print("trying: " + next + ": ");
        if (maze.isOffLimits(next) || !maze.isPassable(next)) {
            System.out.println("impassable");
            return false;
        }

        if (maze.isExit(next.x, next.y)) {
            if (!next.equals(start)) {
                // solved
                route.add(next);
                solvable = true;
            }
            done = true;
        } else {
            // remove possible loops
            boolean deleteMode = false;
            for (Iterator<Coordinate> iCoord = route.iterator(); iCoord.hasNext(); ) {
                Coordinate c = iCoord.next();
                if (deleteMode) {
                    iCoord.remove();
                } else if (c.equals(next)) {
                    iCoord.remove();
                    deleteMode = true;
                    System.out.print("backtracing to " + next + "... ");
                }
            }
            route.add(next);
            currPos = next;
        }
        System.out.println("moved");
        return true;
    }

    public static class Coordinate {
        public int x;
        public int y;

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

        @Override
        public String toString() {
            return "(" + x + ", " + y + ")";
        }

        @Override
        public boolean equals(Object obj) {
            return ((Coordinate)obj).x == x && ((Coordinate)obj).y == y;
        }

        @Override
        public int hashCode() {
            final int PRIME = 31;
            int result = 1;
            result = PRIME * result + x;
            result = PRIME * result + y;
            return result;
        }

        public Coordinate move(int direction) {
            switch (direction) {
                case -2: // left
                    return new Coordinate(x - 1, y);
                case -1: // up
                    return new Coordinate(x, y - 1);
                case 1: // down
                    return new Coordinate(x, y + 1);
                case 2: // right
                    return new Coordinate(x + 1, y);
                default:
                    throw new IllegalArgumentException("Invalid direction: " + direction);
            }
        }
    }

    public static class Maze {
        private int[] grid;
        private int height;
        private int length;

        public Maze(int[] grid, int length) {
            this.grid = grid;
            this.length = length;
            height = grid.length / length;
        }

        public boolean isPassable(Coordinate c) {
            return grid[c.y * length + c.x] == 1;
        }

        public boolean isExit(int x, int y) {
            return x == 0 || y == 0 || x == (length - 1) || y == height - 1;
        }

        public boolean isOffLimits(Coordinate c) {
            return c.x < 0 || c.y < 0 || c.x >= length || c.y >= height;
        }

        public int getLength() {
            return length;
        }

        public int getHeight() {
            return height;
        }

        public int getCell(int x, int y) {
            return grid[y * length + x];
        }
    }

    // all test code from here down
    public void printRoute() {
        System.out.println("Solvable: " + solvable);
        for (int y = 0; y < maze.getHeight(); y++) {
            for (int x = 0; x < maze.getLength(); x++) {
                Coordinate c = new Coordinate(x, y);
                if (route.contains(c)) {
                    if (c.equals(start)) {
                        System.out.print('s');
                    } else {
                        System.out.print('x');
                    }
                } else {
                    System.out.print(maze.getCell(x, y));
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // "2" marks the starting point.
        testMaze(new int[] {
                0, 0, 0, 0,
                2, 0, 0, 0,
                0, 0, 0, 0
            }, 4);

        testMaze(new int[] {
                0, 0, 0, 0,
                2, 1, 1, 0,
                0, 0, 0, 0
            }, 4);

        testMaze(new int[] {
                0, 0, 0,
                2, 1, 0,
                0, 1, 0
            }, 3);

        testMaze(new int[] {
                0, 0, 0, 0, 0,
                2, 1, 0, 1, 0,
                0, 1, 1, 1, 0,
                0, 1, 0, 0, 0,
                0, 1, 1, 1, 1,
                0, 0, 0, 0, 0,
            }, 5);

        testMaze(new int[] {
                0, 0, 0, 0, 0, 0,
                0, 0, 0, 1, 1, 0,
                2, 1, 0, 1, 1, 0,
                0, 1, 1, 1, 1, 0,
                0, 1, 0, 0, 0, 0,
                0, 1, 1, 1, 1, 0,
                0, 0, 0, 1, 1, 0,
                0, 0, 0, 1, 0, 0,
                0, 0, 0, 1, 0, 0
            }, 6);

        testMaze(new int[] {
                0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 1, 1, 1, 0,
                2, 1, 0, 1, 0, 1, 0,
                0, 1, 1, 1, 1, 1, 0,
                0, 1, 0, 0, 0, 0, 0,
                0, 1, 1, 1, 1, 1, 1,
                0, 0, 0, 1, 0, 0, 0,
                0, 0, 0, 1, 0, 0, 0,
                0, 0, 0, 1, 0, 0, 0
            }, 7);
    }

    public static void testMaze(int[] maze, int length) {
        Coordinate start = null;
        for (int i = 0; i < maze.length; i++) {
            if (maze[i] == 2) {
                maze[i] = 1;
                start = new Coordinate(i % (i / length), i / length);
            }
        }

        System.out.println("Starting at: " + start);
        MazeSolver ms = new MazeSolver(new Maze(maze, length), start);
        ms.solve();
        ms.printRoute();
    }
}