// Displays a single self-avoiding random walk

public class ShowOneWalk {

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);       // lattice size
        int deadEnds = 0;                        // trials resulting in a dead end

        StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
        StdDraw.setXscale(0, N);
        StdDraw.setYscale(0, N);
        for (int x = 0; x < N; x++) {
            StdDraw.line(x,0, x, N - 1);
        }
        for (int y = 0; y < N; y++) {
            StdDraw.line(0,y, N - 1, y);
        }

        // simulate 1 self-avoiding walk
        boolean[][] a = new boolean[N][N];   // intersections visited
        int x = N/2, y = N/2;                // current position
        StdDraw.setPenColor(StdDraw.GREEN);
        StdDraw.filledCircle(x, y, 0.20);

        StdDraw.setPenColor(StdDraw.BLUE);

        // repeatedly take a random step, unless you've already escaped
        while (x > 0 && x < N-1 && y > 0 && y < N-1)  {

            // dead-end, so break out of loop
            if (a[x-1][y] && a[x+1][y] && a[x][y-1] && a[x][y+1]) {
                deadEnds++;
                StdDraw.setPenColor(StdDraw.RED);
                StdDraw.filledCircle(x, y, 0.20);
                break;
            }

            // mark (x, y) as visited
            a[x][y] = true;

            // take a random step to unvisited neighbor
            double r = Math.random();
            if (r < 0.25) {
                if (!a[x+1][y]) {
                    x++;
                    StdDraw.line(x-1, y, x, y);
                }
            }
            else if (r < 0.50) {
                if (!a[x-1][y]) {
                    x--;
                    StdDraw.line(x+1, y, x, y);
                }
            }
            else if (r < 0.75) {
                if (!a[x][y+1]) {
                    y++;
                    StdDraw.line(x, y-1, x, y);
                }
            }
            else if (r < 1.00) {
                if (!a[x][y-1]) {
                    y--;
                    StdDraw.line(x, y+1, x, y);
                }
            }

            // Use a delay loop here to slow the action down...
            for (int i = 0; i < Integer.MAX_VALUE/10; i++)
                ;
        }
        if (deadEnds > 0)
            System.out.println("Dead End");

    }

}