1.走迷宫算法思想 走迷宫有很多种实现方式，包括： (1)递归: a.创建一个存储通路结点的栈Stack。 b.从矩阵的第一个结点(0,0)开始，将(0,0)结点压入栈中,顺时针从右->下->左->上寻找通路结点(这里我的设计是值为1的就是通路，值为0的就不是通路，这里的通路结点是要在通向目的结点那条道上的结点)，将每个通路结点压入栈中，直到找到的通路结点是目的结点。 c.设置一个判断是否已经访问过的数组boolean visited[][]，如果结点已经访问过，将数组中对应位置的值设置为true。 d.对于通路结点的选择，要判断是否在边界内，以及是否曾经压入栈中，也就是是否曾经访问过。 (2)深度优先搜索遍历 (3)广度优先搜索遍历 2.算法代码实现
/** * @description 迷宫结点 * @author liuffei * @date 2017-07 */ public class MazeNode { private int row;//结点行数 private int col;//结点列数 public MazeNode(int row,int col){ this.row = row; this.col = col; } public int getRow() { return row; } public void setRow(int row) { this.row = row; } public int getCol() { return col; } public void setCol(int col) { this.col = col; } } import java.util.Stack; /** * @description 寻找迷宫的出路 * @author liuffei * @date 2017-06-16 */ public class MazeRoute { //创建存储路过结点的栈 public Stack<MazeNode> stack = new Stack<MazeNode>(); //maze中的结点为1表示是通路，0表示不是通路 public Stack findRoute(int[][] maze){ MazeNode beginNode = new MazeNode(0,0);//进入结点 stack.push(beginNode); //对于一个结点，从它的右-下-左-上顺时针进行遍历。判断当前节点的邻结点是否为通路，如果是的话，就压入栈中，继续寻找下一个通路。 int x = maze.length;//迷宫矩阵的行数 int y = maze[0].length;//迷宫矩阵的列数 int i = 0,j = 0;//i,j表示当前移动的位置 boolean visited[][] = new boolean[x][y];//标志结点是否有访问过 visited[0][0] = true; while(i < x - 1 || j < y - 1){ MazeNode nextNode = getNext(beginNode,maze,visited); if(nextNode.getRow() != beginNode.getRow() || nextNode.getCol() != beginNode.getCol()){ stack.push(nextNode); beginNode = nextNode; } i = nextNode.getRow(); j = nextNode.getCol(); } return stack; } //寻找当前结点的下一个通路 current表示当前结点 public MazeNode getNext(MazeNode current,int[][] maze,boolean visited[][]){ //表示下一个通路结点 MazeNode next = null; int x = maze.length;//迷宫矩阵的行数 int y = maze[0].length;//迷宫矩阵的列数 //当前结点current的上下左右结点中一定有一个结点是isWalk = true的。如果其他位置的三个结点都不是通路，则回到这个结点。 //current所在位置 int col = current.getCol(); int row= current.getRow(); //栈顶元素 MazeNode top = stack.peek(); //判断当前结点的右结点(row,col+1)是否是通路， if(col + 1 < y && maze[row][col+1] == 1 && !visited[row][col+1]){ next = new MazeNode(row,col+1); visited[row][col+1] = true; }else{ //如果右节点不是通路,寻找下结点 if(row + 1 < x && maze[row+1][col] == 1 && !visited[row+1][col]){ next = new MazeNode(row+1,col); visited[row+1][col] = true; }else{ //如果下节点不是通路,寻找左结点 if(col - 1 >= 0 && maze[row][col-1] == 1 && !visited[row][col-1]){ next = new MazeNode(row,col-1); visited[row][col-1] = true; }else{ //如果左结点不是通路，寻找上结点 if(row - 1 >= 0 && maze[row-1][col] == 1 && !visited[row-1][col]){ next = new MazeNode(row-1,col); visited[row-1][col] = true; }else{ //如果上结点都不是通路，就回到栈的栈顶位置。 next = top; } } } } return next; } } import java.util.Stack; /** * 走迷宫算法测试 * @author liuffei * @date 2017年7月10日 * @description */ public class MazeMain { public static void main(String[] args) { int maze[][] = { {1,0,1,0,0,1,0}, {1,0,0,0,1,0,1}, {1,0,1,1,1,0,0}, {1,1,1,0,1,1,1}, {0,1,0,0,1,0,1}, {0,0,0,0,0,0,1} }; MazeRoute mazeRoute = new MazeRoute(); Stack stack = mazeRoute.findRoute(maze); while(!stack.isEmpty()){ MazeNode node = (MazeNode) stack.pop(); System.out.println("("+node.getRow()+","+node.getCol()+")"); } } }3.效果展示
