题目介绍
迷宫问题（栈）
有一个迷宫地图，有一些可达的位置，也有一些不可达的位置（障碍、墙壁、边界）。从当前位置到下一个位置只能通过向上（或者向右、或者向下、或者向左）走一步来实现，从起点出发，如何找到一条到达终点的通路。
用二维矩阵来模拟迷宫地图，1代表该位置不可达，0代表该位置可达。每走过一个位置就将地图的对应位置标记，以免重复。找到通路后打印每一步的坐标，最终到达终点位置。
Input
题目思路
利用广度搜索法，遍历能找到的结点并标记，然后用另外一个数组来记录走过的路径。
具体代码
package com.dreamchaser; import java.util.LinkedList; import java.util.Queue; /** * 迷宫问题（栈） * */ public class test1 { int m=8; int n=8; static int[][] maze={{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}}; public static void main(String[] args) { Queue<Node> queue=new LinkedList<Node>(); queue.add(new Node(1,1,null)); while (!queue.isEmpty()){ Node node=queue.poll(); Node temp; //将相邻的可达点加入队列 do { temp=find(node); if (temp!=null){ queue.add(temp); } }while (temp!=null); if (node.x==8&&node.y==8){ print(node); } } } /** * 递归输出 * @param node */ private static void print(Node node) { if (node.pre==null){ System.out.println("("+node.x+","+node.y+")"); }else { print(node.pre); System.out.println("("+node.x+","+node.y+")"); } } /** * 往四个方向寻找一个可以到达的点 */ private static Node find(Node node){ if (maze[node.x+1][node.y]==0){ //标记已经到达过 maze[node.x+1][node.y]=2; return new Node(node.x+1, node.y, node); } if (maze[node.x-1][node.y]==0){ maze[node.x-1][node.y]=2; return new Node(node.x-1, node.y, node); } if (maze[node.x][node.y+1]==0){ maze[node.x][node.y+1]=2; return new Node(node.x, node.y+1, node); } if (maze[node.x][node.y-1]==0){ maze[node.x][node.y-1]=2; return new Node(node.x, node.y-1, node); } return null; } static class Node{ int x; int y; Node pre; public Node(int x, int y, Node pre) { this.x = x; this.y = y; this.pre = pre; } } }
运行截图
