/*************************************************************************
 *  Compilation:  javac Maze.java
 *  Execution:    java Maze.java N
 *  Dependencies: Cell.java Draw.java
 *
 *  Generates a perfect N-by-N maze using depth-first search with a stack.
 *
 *  % java Maze 62
 *
 *  Note: this program generalizes nicely to finding a random tree in
 *        a graph.
 *************************************************************************/

import java.awt.Color;

public class Maze {
   private int N;                 // dimension of maze
   private Cell cells[][];        // two dimensional grid of cells
   private Cell start, finish;
   private Draw draw;
   private double size;
   boolean done = false;

   Maze(int N) {
      this.N = N;
      draw = new Draw(512, 512);
      size = 512.0 / (N + 2);
      init();
      generate();
   }

   private void init() {

      // need to allocate memory for 2d array, each row, and each cell
      // individually since it's a 2d array of objects and not primitive types
      // use N+2 to leave room for one cell border around N-by-N grid
      cells = new Cell[N+2][N+2];
      for (int x = 0; x < N+2; x++)
         cells[x] = new Cell[N+2];
      for (int x = 0; x < N+2; x++)
         for (int y = 0; y < N+2; y++)
            cells[x][y] = new Cell(x * size, y * size);

      // initialize border cells as already visited
      for (int x = 0; x < N+2; x++) {
         cells[x][0].setVisited(true);
         cells[x][N+1].setVisited(true);
      }

      for (int y = 0; y < N+2; y++) {
         cells[0][y].setVisited(true);
         cells[N+1][y].setVisited(true);
      }

      // Set neighbors, ignoring border cells. (1, 1) is lower left.
      for (int x = 1; x <= N; x++) {
         for (int y = 1; y <= N; y++) {
            Cell north = cells[x][y+1];
            Cell south = cells[x][y-1];
            Cell west  = cells[x-1][y];
            Cell east  = cells[x+1][y];
            cells[x][y].setNeighbors(north, east, south, west);
         }
      }

      // set start and finish states
      start  = cells[1][1];
      finish = cells[N][1];
      draw.setColor(Color.RED);
      start.spot(draw, size);
      finish.spot(draw, size);
   }

   // generate the maze
   private void generate(Cell x) {
      x.setVisited(true);
      Cell next;
      while ((next = x.deleteRandomWall()) != null)
         generate(next);         
   }

   // generate the maze starting from the start cell
   private void generate() {
      generate(start);
      for (int x = 1; x <= N; x++)
         for (int y = 1; y <= N; y++)
            cells[x][y].setVisited(false);

      // delete some random walls
      for (int i = 0; i < N; i++) {
          int x = (int) (1 + Math.random() * N);
          int y = (int) (1 + Math.random() * N);
          cells[x][y].deleteRandomWall();
      }
   }

   // solve the maze using depth first search
   private void solve(Cell x) {
      if (done || x == null || x.isVisited()) return;
      x.setVisited(true);

      if (x == finish) done = true;

      draw.setColor(Color.BLUE);
      x.spot(draw, size);
      draw.show();
      draw.pause(30);

      solve(x.getNorth());
      solve(x.getEast());
      solve(x.getSouth());
      solve(x.getWest());

      if (done) return;

      draw.setColor(Color.GRAY);
      x.spot(draw, size);
      draw.show();
      draw.pause(30);
   }

   // solve the maze starting from the start state
   public void solve() {
      for (int x = 1; x <= N; x++)
         for (int y = 1; y <= N; y++)
            cells[x][y].setVisited(false);
      done = false;
      solve(start);
   }

   // display the maze in a window
   public void draw() {
      if (cells == null) return;
      draw.setColor(Color.BLACK);
      for (int x = 1; x <= N; x++)
         for (int y = 1; y <= N; y++)
            cells[x][y].draw(draw, size);
      draw.show();
   }



   // a test client
   public static void main(String[] args) {
      int N = Integer.parseInt(args[0]);
      Maze maze = new Maze(N);
      maze.draw();
      maze.solve();
   }

}