// Maze.java
// Robert Sedgewick and Kevin Wayne
// Slightly reformatted by Andrew Davison, Nov. 2022

// https://algs4.cs.princeton.edu/41graph/Maze.java.html

/* Generate and solve a maze.

   Usage:
     > compile Maze.java
     > run Maze <size>
   e.g.
     > run Maze 20
*/


import java.io.*;
import java.util.*;


public class Maze
{
  private int size;                   // dimension of maze

  private boolean[][] north;       // is there a wall to north of cell i, j
  private boolean[][] east;
  private boolean[][] south;
  private boolean[][] west;

  private boolean[][] visited;
  private boolean isSolved = false;

  private Random rand = new Random();


  public Maze(int n)
  {
    size = n;
    StdDraw.setXscale(0, size+2);
    StdDraw.setYscale(0, size+2);
    initMaze();
    generate();
  }


  private void initMaze()
  {
    // initialize border cells as already visited
    visited = new boolean[size+2][size+2];
    for (int x = 0; x < size+2; x++) {
      visited[x][0] = true;
      visited[x][size+1] = true;
    }

    for (int y = 0; y < size+2; y++) {
      visited[0][y] = true;
      visited[size+1][y] = true;
    }

    // initialze all walls as present
    north = new boolean[size+2][size+2];
    east  = new boolean[size+2][size+2];
    south = new boolean[size+2][size+2];
    west  = new boolean[size+2][size+2];
    for (int x = 0; x < size+2; x++)
      for (int y = 0; y < size+2; y++) {
        north[x][y] = true;
        east[x][y]  = true;
        south[x][y] = true;
        west[x][y]  = true;
      }
  } // end of initMaze()


  private void generate()
  // generate the maze starting from lower left
  {
    genBT(1, 1);

    // delete some random walls
    for (int i = 0; i < size; i++) {
      int x = 1 + rand.nextInt(size-1);
      int y = 1 + rand.nextInt(size-1);
      north[x][y] = south[x][y+1] = false;
    }

    // add some random walls
    for (int i = 0; i < 10; i++) {
      int x = size/2 + rand.nextInt(size/2);
      int y = size/2 + rand.nextInt(size/2);
      east[x][y] = west[x+1][y] = true;
    }

  } // end of generate()



  private void genBT(int x, int y)
  // generate the maze with recursion
  {
    visited[x][y] = true;

    // while there is an unvisited neighbor
    while (!visited[x][y+1] || !visited[x+1][y] || 
           !visited[x][y-1] || !visited[x-1][y])

      // pick random neighbor
      while (true) {
        double r = rand.nextInt(4);
        if ((r == 0) && !visited[x][y+1]) {
          north[x][y] = false;
          south[x][y+1] = false;
          genBT(x, y + 1);
          break;
        }
        else if ((r == 1) && !visited[x+1][y]) {
          east[x][y] = false;
          west[x+1][y] = false;
          genBT(x+1, y);
          break;
        }
        else if ((r == 2) && !visited[x][y-1]) {
          south[x][y] = false;
          north[x][y-1] = false;
          genBT(x, y-1);
          break;
        }
        else if ((r == 3) && !visited[x-1][y]) {
          west[x][y] = false;
          east[x-1][y] = false;
          genBT(x-1, y);
          break;
        }
      }
  } // end of genBT()




  public void solve()
  {
    for (int x = 1; x <= size; x++)
      for (int y = 1; y <= size; y++)
        visited[x][y] = false;
    isSolved = false;
    solveBT(1, 1);

    System.out.println("Solved? " + isSolved);
  } // end of solve()


  private void solveBT(int x, int y)
  // solve the maze using recursion
  {
    if ((x == 0) || (y == 0) || (x == size+1) || (y == size+1)) 
      return;
    if (isSolved || visited[x][y]) 
      return;

    visited[x][y] = true;
    StdDraw.setPenColor(StdDraw.BLUE);
    StdDraw.filledCircle(x + 0.5, y + 0.5, 0.25);   // visiting (x,y)
    StdDraw.pause(30);

    // reached middle of maze (the end)
    if ((x == size/2) && (y == size/2)) 
      isSolved = true;

    if (!north[x][y]) 
      solveBT(x, y + 1);
    if (!east[x][y]) 
      solveBT(x + 1, y);
    if (!south[x][y]) 
      solveBT(x, y - 1);
    if (!west[x][y]) 
      solveBT(x - 1, y);

    if (isSolved) 
      return;

    // gray means we are backtracking over this (x,y) move
    StdDraw.setPenColor(StdDraw.GRAY);
    StdDraw.filledCircle(x + 0.5, y + 0.5, 0.25);
    StdDraw.pause(30);
  } // end of solveBT()




  public void drawMaze()
  {
    StdDraw.setPenColor(StdDraw.RED);
    StdDraw.filledCircle(size/2.0 + 0.5, size/2.0 + 0.5, 0.375);
    StdDraw.filledCircle(1.5, 1.5, 0.375);

    StdDraw.setPenColor(StdDraw.BLACK);
    for (int x = 1; x <= size; x++)
      for (int y = 1; y <= size; y++) {
        if (south[x][y]) 
          StdDraw.line(x, y, x+1, y);
        if (north[x][y]) 
          StdDraw.line(x, y+1, x+1, y+1);
        if (west[x][y]) 
          StdDraw.line(x, y, x, y+1);
        if (east[x][y]) 
          StdDraw.line(x+1, y, x+1, y+1);
      }
    // StdDraw.show();
    StdDraw.pause(1000);
  } // end of drawMaze()


  // ----------------- test rig ------------------------


  public static void main(String[] args)
  {
    if (args.length != 1) {
      System.out.println("Usage: java Maze <size>");
      System.exit(1);
    }

    Maze m = new Maze(Integer.parseInt(args[0]));
    m.drawMaze();
    m.solve();
  } // end of main()


}