import javax.swing.*;
import java.awt.*;
import java.util.*;
import java.util.List;
/**
* Created by 伟大的华仔 on 2017-11-30.
*/
public class Maze extends JFrame {
private int row;//行数
private int col; //列数
private DisJoinSet disjSet;
private int winHeight=1000;// 行高
private int winWidth=1000;//行宽
public Maze(int row,int col){
this.row = row;
this.col = col;
this.setTitle("迷宫");//设置标题
this.setSize(winWidth,winHeight);//设置组件大小
this.setVisible(true);//显示或隐藏此 Window
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);//设置用户在此窗体上发起 "close" 时默认执行的操作 EXIT_ON_CLOSE（在 JFrame 中定义）：使用 System exit 方法退出应用程序
}
public static void main(String[] args) {
/**
* 定义迷宫的大小，必须是正方形的
* */
int rowCount = 100;
int colCount = 100;
Maze maze = new Maze(rowCount,colCount);
}
@Override
public void paint(Graphics g){
super.paint(g);
/**
* 申请一个String集合，放置合并的节点
* */
List<Integer>DisList = new LinkedList<>();
//背景为白色
g.setColor(Color.white);
g.fillRect(0, 0, winWidth, winHeight);//窗口填充矩形
g.setColor(Color.black);
final int extraWidth = 20;
final int cellWidth = (winWidth-2*extraWidth)/row;//定义每个格子的宽度
final int cellHeight = (winHeight-4*extraWidth)/col;//定义每个格子的高度
for(int i=0;i<row;i++) {
for(int j=0;j<col;j++)
{
//初始化m*n矩阵格子
g.drawRect(i*cellWidth+extraWidth,j*cellHeight+2*extraWidth, cellWidth, cellHeight);
}
}
int lastPos = getLastElePos();//迷宫最后一个格式的代表数字
//起点，终点特殊处理
g.setColor(Color.red);
g.fillRect(extraWidth, 2*extraWidth, cellWidth, cellHeight);
g.fillRect((lastPos% row)*cellWidth + extraWidth,(lastPos/ row)*cellHeight + 2*extraWidth, cellWidth, cellHeight);
this.setDisjSet(new DisJoinSet(row*col));
// 路径记录操作
ArrayList<LinkedList<Integer>> adjoinTable = new ArrayList();
Stack<Integer> pathSearch = new Stack<Integer>();
pathSearch.push(0);
for (int i = 0;i<row*col;i++){
LinkedList<Integer> temp = new LinkedList<Integer>();
temp.add(i);
adjoinTable.add(temp);
temp.clear();
}
g.setColor(Color.white); //用后景色擦色
while(disjSet.find(0) != disjSet.find(lastPos)){//如果起点和终点还没在同一个等价类
/*
* 在迷宫内随机挖一个点，再找到该点周围一点，使这两个点落在同一个等价类
*/
Random random = new Random();
int randPos = random.nextInt(lastPos+1);//+1是为了能随机到最后一位
int rowIndex = randPos % row;
int colIndex = randPos / col;
List<Integer> neighborPos = getNeighborNums(rowIndex, colIndex) ;
int randNeighbor = neighborPos.get(random.nextInt(neighborPos.size()));
if(disjSet.find(randPos) == disjSet.find(randNeighbor)){//两点在同一个等价类
continue;
}else{
int aRoot = disjSet.find(randPos);
int bRoot = disjSet.find(randNeighbor);
disjSet.union(aRoot, bRoot);
DisList.add(randPos);
DisList.add(randNeighbor);
// /**
// * 打印搜索过程
// * */
// System.out.println("***过程分析*****************"+Arrays.toString(this.disjSet.getEleRoots()));
int maxNum = Math.max(randPos, randNeighbor);//取得较大点
int x1=0,y1=0,x2=0,y2=0;
if(Math.abs(randPos-randNeighbor) == 1){//说明在同一行，用竖线隔开
x1= x2=(maxNum% row)*cellWidth + extraWidth;
y1=(maxNum/ row)*cellHeight + 2*extraWidth;
y2=y1+cellHeight;
}else{//说明在同一列，用横线隔开
y1=y2=(maxNum/ row)*cellHeight + 2*extraWidth;
x1=(maxNum% row)*cellWidth + extraWidth;
x2=x1+cellWidth;
}
g.drawLine(x1, y1, x2, y2);
}
}
long start = System.currentTimeMillis();
/**
* 打印数组
* */
// System.out.println("***最终结构********************"+Arrays.toString(this.disjSet.getEleRoots()));
// for (Iterator it = DisList.iterator();it.hasNext();){
// System.out.println("***节点***"+it.next());
// }
for (int i = 0;i<DisList.size();i=i+2){
adjoinTable.get(DisList.get(i)).add(DisList.get(i+1));
adjoinTable.get(DisList.get(i+1)).add(DisList.get(i));
}
// for (int i = 0;i<adjoinTable.size();i++){
// System.out.println("链表内容"+Arrays.toString(adjoinTable.get(i).toArray()));
// }
/**
* 算法步骤
* 1、检索i节点的联通节点
* 2、存在就放入栈中（前提为栈中没有该元素），不存在弹出栈顶元素（删除邻接表中的数据），或者为终点元素结束
* 3、重复步骤1
* */
while (true){//while开始
if (pathSearch.isEmpty()){
System.out.println("栈为空，迷宫没有路径");
break;
}
if (pathSearch.peek()==(row*col-1)){
System.out.println("迷宫已破解");
break;
}
if (adjoinTable.get(pathSearch.peek()).size()==1 && pathSearch.peek() != 0){
Integer temp = pathSearch.pop();
if(pathSearch.isEmpty()){
System.out.println("栈为空，迷宫没有路径");
break;
}else {
adjoinTable.get(pathSearch.peek()).remove(temp);
adjoinTable.get(temp).remove(pathSearch.peek());
}
}else {
if (pathSearch.search(adjoinTable.get(pathSearch.peek()).get(0))!= -1 ){
if (adjoinTable.get(pathSearch.peek()).size()>1){
pathSearch.push(adjoinTable.get(pathSearch.peek()).get(1));
// Iterator<Integer> boy = adjoinTable.get(pathSearch.peek()).listIterator();
// while (boy.hasNext()){
// int girl = boy.next();
// if (!pathSearch.contains(girl)){
// pathSearch.push(girl);
// }
// }
}
}else {
pathSearch.push(adjoinTable.get(pathSearch.peek()).get(0));
}
}
}//while结束
/**
* 输出路径
* */
// System.out.println("迷宫路径"+Arrays.toString(pathSearch.toArray()));
g.setColor(Color.red);
while (!pathSearch.isEmpty()){
int boy = pathSearch.pop();
//左右
g.fillOval((boy% row)*cellWidth + cellWidth/4+extraWidth,(boy/ row)*cellHeight + cellHeight/4+2*extraWidth, cellWidth/2, cellHeight/2);
}
//
long end = System.currentTimeMillis();
System.out.println("时间流程："+Long.toString(end-start)+"ms");
adjoinTable.clear();
pathSearch.clear();
}
/**
* 取得目标坐标点周围四个有效点
*/
public List<Integer> getNeighborNums(int rowIndex,int colIndex){
List<Integer> neighborPos = new ArrayList<Integer>(4);
//右元素
if(isPointInMaze(rowIndex+1,colIndex)){
neighborPos.add(getCoordinateNum(rowIndex+1,colIndex));
}
//下元素
if(isPointInMaze(rowIndex,colIndex+1)){
neighborPos.add(getCoordinateNum(rowIndex,colIndex+1));
}
//左元素
if(isPointInMaze(rowIndex-1,colIndex)){
neighborPos.add(getCoordinateNum(rowIndex-1,colIndex));
}
//上元素
if(isPointInMaze(rowIndex,colIndex-1)){
neighborPos.add(getCoordinateNum(rowIndex,colIndex-1));
}
return neighborPos;
}
public int getLastElePos(){
return row*col-1;
}
public DisJoinSet getDisjSet() {
return disjSet;
}
public void setDisjSet(DisJoinSet disjSet) {
this.disjSet = disjSet;
}
/**
* 根据坐标返回对应的值
* 例如在4*3矩阵，(0，0)返回0;(3,2)返回10
*/
public int getCoordinateNum(int x,int y){
return y*col + x;
}
/**
* 判断给定坐标是否在迷宫矩阵内
*/
public boolean isPointInMaze(int x,int y){
if(x < 0 || y < 0) return false;
return x < row && y <col;
}
}
目前状态：100x100的求解需要5s，200x200的需要20s左右。
问题：paint函数重画存在闪烁问题。求解路径算法需要优化。
