package maze;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Stack;
public class Maze 
{
 int len = 11; //迷宮長度
 int wid = 11; //迷宮寬度
 char wall = '■'; //代表墻
 char blank = '○'; //代表空地
 char[][] maze; //迷宮
 boolean[][] visit; //用來標記某一格是否被訪問過
 Node start = new Node(0,0); //開始節點
 Node exit = new Node(len - 1, wid - 1); //出口，其實現在也沒什么用，因為沒有交互只是生成了一個迷宮而已
 Node cur; //當前格
 Node next; //下一格
 Stack<Node> path = new Stack<Node>(); //表示路徑的棧
 int[][] adj = {
  {0,2},{0,-2},{2,0},{-2,0}
 }; //用來計算鄰接格
 /**
 * 迷宮的格子類
 * @author Yan
 */
 class Node
 {
 int x,y;
 public Node(){}
 public Node(int x, int y)
 {
  this.x = x;
  this.y = y;
 }
 public String toString() {
  return "Node [x=" + x + ", y=" + y + "]";
 }
 }
 /**
 * 初始化，初始化迷宮參數
 */
 void init()
 {
 maze = new char[len][wid];
 visit = new boolean[len][wid];
 for(int i = 0; i < len; i++)
 {
  for(int j = 0; j < wid; j++)
  {
  maze[i][j] = wall;
  visit[i][j] = false;
  }
 }
 visit[start.x][start.y] = true;
 maze[start.x][start.y] = blank;
 cur = start; //將當前格標記為開始格
 }
 /**
 * 打印結果
 */
 void printMaze()
 {
 for(int i = 0; i < len; i++)
 {
  for(int j = 0; j < wid; j++)
  {
  System.out.print(maze[i][j] + " ");
//  if(maze[i][j] == '○')
//  {
//   System.err.print(maze[i][j] + " ");
//  }
//  else
//  {
//   System.out.print(maze[i][j] + " ");
//  }
//  try {
//   Thread.sleep(100);
//  } catch (InterruptedException e) {
//   e.printStackTrace();
//  }
  }
  System.out.println();
 }
 System.out.println("==========================================");
 }
 /**
 * 開始制作迷宮
 */
 void makeMaze()
 {
 path.push(cur); //將當前格壓入棧
 while(!path.empty())
 {
  Node[] adjs = notVisitedAdj(cur);//尋找未被訪問的鄰接格
  if(adjs.length == 0)
  {
  cur = path.pop();//如果該格子沒有可訪問的鄰接格，則跳回上一個格子
  continue;
  }
  next = adjs[new Random().nextInt(adjs.length)]; //隨機選取一個鄰接格
  int x = next.x;
  int y = next.y;
  //如果該節點被訪問過，則回到上一步繼續尋找
  if(visit[x][y])
  {
  cur = path.pop();
  }
  else//否則將當前格壓入棧，標記當前格為已訪問，并且在迷宮地圖上移除障礙物
  {
  path.push(next);
  visit[x][y] = true;
  maze[x][y] = blank;
  maze[(cur.x + x) / 2][(cur.y + y) / 2] = blank; //移除當前格與下一個之間的墻壁
  cur = next;//當前格等于下一格
  }
 }
 }
 /**
 * 判斷節點是否都被訪問
 * @param ns
 * @return
 */
 boolean allVisited(Node[] ns)
 {
 for(Node n : ns)
 {
  if(!visit[n.x][n.y])
  return false;
 }
 return true;
 }
 /**
 * 尋找可訪問的鄰接格，這里可以優化，不用list
 * @param node
 * @return
 */
 Node[] notVisitedAdj(Node node)
 {
 List<Node> list = new ArrayList<Node>();
 for(int i = 0; i < adj.length; i++)
 {
  int x = node.x + adj[i][0];
  int y = node.y + adj[i][1];
  if( x >= 0 && x < len && y >= 0 && y < wid)
  {
  if(!visit[x][y])
   list.add(new Node(x,y));
  }
 }
 Node[] a = new Node[list.size()];
 for(int i = 0; i < list.size(); i++)
 {
  a[i] = list.get(i);
 }
 return a;
 }
 /**
 * 入口方法
 * @param args
 */
 public static void main(String[] args) {
 Maze m = new Maze();
 m.init();
 m.makeMaze();
 m.printMaze();
 }
}