迷宫问题的求解（回溯法、深度优先遍历、⼴度优先遍历）⼀、问题介绍 有⼀个迷宫地图，有⼀些可达的位置，也有⼀些不可达的位置（障碍、墙壁、边界）。
从⼀个位置到下⼀个位置只能通过向上（或者向右、或者向下、或者向左）⾛⼀步来实现，从起点出发，如何找到⼀条到达终点的通路。
本⽂将⽤两种不同的解决思路，四种具体实现来求解迷宫问题。
⽤⼆维矩阵来模拟迷宫地图，1代表该位置不可达，0代表该位置可达。
每⾛过⼀个位置就将地图的对应位置标记，以免重复。
找到通路后打印每⼀步的坐标，最终到达终点位置。
封装了点Dot，以及深度优先遍历⽤到的Block，⼴度优先遍历⽤到的WideBlock。
private int[][] map = { //迷宫地图,1代表墙壁，0代表通路{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};private int mapX = map.length - 1; //地图xy边界private int mapY = map[0].length - 1;private int startX = 1; //起点private int startY = 1;private int endX = mapX - 1; //终点private int endY = mapY - 1; //内部类，封装⼀个点public class Dot{private int x; //⾏标private int y; //列标public Dot(int x , int y) {this.x = x;this.y = y;}public int getX(){return x;}public int getY(){return y;}}//内部类，封装⾛过的每⼀个点,⾃带⽅向public class Block extends Dot{private int dir; //⽅向,1向上，2向右，3向下，4向左public Block(int x , int y) {super(x , y);dir = 1;}public int getDir(){return dir;}public void changeDir(){dir++;}}/*⼴度优先遍历⽤到的数据结构，它需要⼀个指向⽗节点的索引*/public class WideBlock extends Dot{private WideBlock parent;public WideBlock(int x , int y , WideBlock p){super(x , y);parent = p;}public WideBlock getParent(){return parent;}}⼆、回溯法 思路：从每⼀个位置出发，下⼀步都有四种选择（上右下左），先选择⼀个⽅向，如果该⽅向能够⾛下去，那么就往这个⽅向⾛，当前位置切换为下⼀个位置。
