迷宫（基于深度优先遍历和广度优先遍历实现）

先将文件拖到项目的根目录下
创建一个主函数

public class Main {
	public static void main(String[] args) {
     //根据文件名创建迷宫数据对象
	AlgoVisualizer maze = new AlgoVisualizer("maze_101_101.txt");
	}
}

创建一个MazeData类
public class MazeData {
public static final char ROAD = ’ ';//定义路为空格
public static final char WALL = ‘#’;//定义墙为#
private int N; //定义成成员变量以便再次进行访问，外界间接访问
private int M;
private char[][] maze;//构建好迷宫数组
public boolean[][] visited; //定义一个记录访问状态数组
public boolean[][] path; //定义一个路径数组
private int entranceX , entranceY;//定义迷宫入口
private int exitX , exitY; //定义迷宫出口
public MazeData(String filename) { //传入文件名

if(filename == null) {   //先判空
				throw new IllegalArgumentException("文件名为空");//为空时抛出异常
			}
			//根据文件名创建该文件对象
			File file = new File(filename);	//创建该文件对象
			Scanner input = null;	//先默认初始化为空
			if(!file.exists())	
				throw new IllegalArgumentException("文件不存在");
			//调用FileInputStream时可能会出错，所以用+++try-catch
			try { //开始读取文件
				FileInputStream fis = new FileInputStream(file);	//创建该文件对象
				input = new Scanner(fis);		//接收该文件
				
				String nmline = input.nextLine();//读取文件内容的第一行
				String[] nm = nmline.split(" ");	//将第一行的内容进行划分
				N = Integer.parseInt(nm[0]);		//定义好迷宫的宽
				M = Integer.parseInt(nm[1]);
				maze = new char[N][M];		//设置好迷宫大小
				visited=new boolean[N][M];//设置访问数组
				path=new boolean[N][M];	//设置路径数组
				for (int i = 0; i < N; i++) {		//嵌套循环对文本内容进行判断并读取到数组中
					String line = input.nextLine();  //将每一行的内容读取到line字符串中
					if(line.length() != M)			//判断读取到该行长度是否与数组的长度相等，文件是否损坏
						throw new IllegalArgumentException("文件内容错误");//不相等抛出异常
					for (int j = 0; j < M; j++) {
						maze[i][j] = line.charAt(j);	//依次将指定角标元素存入到数组中去
					}
				}//for:i
				entranceX = 1; entranceY = 0;		//将迷宫的入口和出口确定
				exitX = N - 2 ; exitY = M - 1;
			} catch (Exception e) {			//捕获异常
				e.printStackTrace();
			}finally {
				if(input !=  null)		//如果读取到的内容不为空时
					input.close();		//关闭I/0流
			}
			
		}
              //构造函数
		//对指定位置进行判断是否在指定范围(迷宫)内
		public boolean inArea(int x , int y) {
			return x >= 0 && x < N && y >= 0 && y < M;
		}
		//获取当前位置的信息
		public char getMaze(int x , int y) {
			 if(!inArea(x, y))	//不在范围内时
				throw new IllegalArgumentException("位置出错");
			return maze[x][y];
		}
		//因为N,M已经private所以间接访问
		public int getN() {
			return N;
		}
		public int getM() {
			return M;
		}
		
		public int getEntranceX(){
			return entranceX;
		}
		public int getEntranceY(){
			return entranceY;
		}
		public int getExitX() {
			return exitX;
		}
		public int getExitY() {
			return exitY;
		}
	}

迷宫的数据已经创建完，将生成的数据转化成图形化界面
导入AlgoFrame（窗口，绘画）、AlgoVisualizer(初始化数据、初始化视图)、AlgoVisHelper（工具类）
1、在AlgoVisualizer中
原来传入的宽高改成文件名，通过文件名创建data数据

public AlgoVisualizer(String fileName){
    	//初始化数据
    	data = new MazeData(fileName);
    	int sceneWidth = data.getM() * BLOCK_SIDE;//根据格子的大小决定屏幕的宽高
        int sceneHeight = data.getN() * BLOCK_SIDE;

设置动画逻辑，先直接绘制，之后具体实现动画逻辑

private void run(){
   frame.render(data); 
}

2、AlgoFrame中
//设置自己的数据

 private MazeData data;
    public void render(MazeData data){//接收数据
        this.data = data;
        repaint();//画布进行重绘
    }

具体绘制
//具体绘制

int w = canvasWidth / data.getM();//每一个格子的宽
   int h = canvasHeight / data.getN();
   for (int i = 0; i < data.getN(); i++) {
    	for (int j = 0; j < data.getM(); j++) {
			if((data.getMaze(i, j) == MazeData.WALL)){//如果是墙时设置成蓝色
				AlgoVisHelper.setColor(g2d, AlgoVisHelper.LightBlue);
			}else {//是路设置成白色
		         	AlgoVisHelper.setColor(g2d, AlgoVisHelper.White);
				}
			if(data.path[i][j] == true)
				AlgoVisHelper.setColor(g2d, AlgoVisHelper.Orange);
				AlgoVisHelper.fillRectangle(g2d, j * w, i * h, w, h);//画一个矩形
				}
			}

1、深度优先遍历-递归方式

if(!go(data.getEntranceX(), data.getEntranceY())) {
    		 throw new IllegalArgumentException("迷宫无解");
    	    }

 
 private boolean go(int x , int y ) {
    	if(!data.inArea(x, y))
    		throw new IllegalArgumentException("遍历越界");
    	data.visited[x][y] = true;
    	setData(x,y,true);//标记为路
    	if(x == data.getExitX() && y == data.getExitY()) {
    		return true;//找到后跳出
    	}
    	for (int i = 0; i < d.length; i++) {
		 	int newX = x + d[i][0];
			int newY = y + d[i][1];
			//非访问/没越界/
			if(data.inArea(newX, newY) && 
				!data.visited[newX][newY] &&
					data.getMaze(newX, newY) == MazeData.ROAD) {
				if(go(newX, newY)) {
					return true;
				}
			}//if:i
			
		}//for
    	setData(x, y,false);
		return false;
    }

标记路
 private void setData(int x ,int y, boolean isPath) {
    	if (data.inArea(x, y)) {
			data.path[x][y] = isPath;//标记为路
		}
    	frame.render(data);//画布接收数据重新绘制
    	AlgoVisHelper.pause(1);//设置探路速度
    }

2、深度优先遍历-非递归方式>栈

定义一个Position类
public class Position {
	private int x,y;
	private Position pre;//当前位置的前一个结点
	public Position(int x,int y,Position pre) {
		this.x=x;
		this.y=y;
		this.pre=pre;
	}
	public int getX() {return x;}
	public int getY() {return y;}
	public Position getPre() {return pre;}
}


 Stack<Position> stack=new Stack<Position>();
        Position entrance=new Position(data.getEntranceX(),data.getEntranceY(),null);//入口的前者为null
        stack.push(entrance);//入口结点进栈
        data.visited[entrance.getX()][entrance.getY()]=true;//当前进入的结点标记已经访问
        boolean isSolved=false;
        while(!stack.empty()) {	//如果栈为空 仅仅表示所有的可能路径查找完毕
        	Position curPosition=stack.pop(); //当前结点弹栈
        	setData(curPosition.getX(),curPosition.getY(),true);//更新路径数据
        	if(curPosition.getX()==data.getExitX()&&curPosition.getY()==data.getExitY()) {
        		//找到出口
        		isSolved=true;
        		findPath(curPosition);//找路径
        		break;
        	}
        	for(int i=0;i<d.length;i++) {
        		int newX=curPosition.getX()+d[i][0];//定义新坐标
        		int newY=curPosition.getY()+d[i][1];
        		if(data.inArea(newX, newY)
        				&&data.getMaze(newX, newY)==MazeData.ROAD
        				&&!data.visited[newX][newY]) {
        			//在范围&&是个路&&未能访问
        			stack.push(new Position(newX, newY, curPosition));//新结点入栈
        			data.visited[newX][newY]=true;//设置已访问状态
        		}
        	}
        }
        //while结束有俩种可能，正常跳出和非正常跳出
        if(!isSolved) {//没有被解决
        	throw new IllegalArgumentException("找不到解决方案");
        }

定义一个findPath类寻找最终路径
        private void findPath(Position des) {//当前结点为des
    	Position cur=des;//cur移动寻找
    	while(cur!=null) {
    		data.result[cur.getX()][cur.getY()]=true;
    		cur=cur.getPre();
    	}
    }

3.广度优先遍历-队列
广度优先遍历所寻找的路径是最短的(一层一层的往下走)

LinkedList<Position> queue=new LinkedList<Position>();//双端队列  
      Position entrance=new Position(data.getEntranceX(),data.getEntranceY(),null);//入口的前者为null   
      queue.addLast(entrance);//尾插法 
      data.visited[entrance.getX()][entrance.getY()] =true;//标记已访问
      boolean isSolved=false;//默认没有被解决
       while(queue.size()!=0) {
    	  Position curPosition =queue.removeFirst();//出队第一个元素并给curPosition接收
    	  setData(curPosition.getX(),curPosition.getY(),true);
    	  if(curPosition.getX()==data.getExitX()&&curPosition.getY()==data.getExitY()) {
    		 isSolved=true;
    		  findPath(curPosition);
    		  break;
    	  }
    	  for(int i=0;i<d.length;i++) {
      		int newX=curPosition.getX()+d[i][0];//定义新坐标
      		int newY=curPosition.getY()+d[i][1];
      		if(data.inArea(newX, newY)
      				&&data.getMaze(newX, newY)==MazeData.ROAD
      				&&!data.visited[newX][newY]) {
      			//在范围&&是个路&&未能访问
      			queue.addLast(new Position(newX, newY, curPosition));//新结点入队
      			data.visited[newX][newY]=true;//设置已访问状态
      		}
      	}
       }