题：
二维数组表示迷宫（格子组成），0不能走，1能走。求走出路径。
指导思想：
一步步尝试出所有可能，输出成功结果。
尝试过程保存在栈里，一旦走出，栈里保存的就是正确路径。
编程思路：
从某个格子开始找：
｛
如果该格子是出口，成功！
某个格子入栈
｛
某个格子上可用，某个格子上开始找
某个格子右可用，某个格子右开始找
某个格子下可用，某个格子下开始找
某个格子左可用，某个格子左开始找
｝
某个格子出栈
｝
编程：
1、先准备数组，并测试：
public class App { static int[][] a; public static void main(String[] args) throws Exception { a = getArray(); showArray(); } public static int[][] getArray() { int[][] x = { { 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1 }, { 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 }, { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1 }, { 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; return x; } public static void showArray() { for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { System.out.print(a[i][j] + "\t"); } System.out.println(); } } }
测试结果：
目测有正确解，通过。
2、写一个简单的栈，用于保存走过的路径：
public class MyStack { public static int[][] n = new int[150][2]; public static int p = 150; public static void push(int x, int y) { p--; n[p][0] = x; n[p][1] = y; } public static int[] pop() { int[] x = new int[2]; if (p == 150)//栈空 { x[0] = -1; x[1] = -1; } else { x[0] = n[p][0]; x[1] = n[p][1]; p++; } return x; } }
3、按之前的思路，搭好“走迷宫”方法的架子
//从（x，y）位置开始走迷宫 public static void goMiGong(int x,int y) { //如果这个格子是出口，则程序结束 if(x==7&&y==12) { //当前格子设置为2 //输出数组 //退出程序 } else { //当前格子设置为2，入栈 //*按上、右、下、左顺序依次走其他格子 //出栈（且还原为1）（栈空则无解） } }
4、回头阅读上面的程序，打星号的部分稍微有一点复杂，希望有一个方法，辅助判断某个格子是否可以走。代码如下：
public static boolean nengZou(int x,int y) { boolean b=false; if(x>=0&&y>=0) { if(a[x][y]==1) { b=true; } } return b; }
5、一切准备完毕，用上面的东西拼装起整个程序。调试后代码如下：
主程序（app.java）
public class App { static int[][] a; // 存放出栈元素的位置，如（3,2） static int[] p = new int[2]; public static void main(String[] args) throws Exception { a = getArray(); System.out.println("原始迷宫："); showArray(); System.out.println("-----------------------------------"); goMiGong(0, 0); } public static int[][] getArray() { int[][] x = { { 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1 }, { 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 }, { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1 }, { 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; return x; } public static void showArray() { for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { System.out.print(a[i][j] + "\t"); } System.out.println(); } } // 从（x，y）位置开始走迷宫 public static void goMiGong(int x, int y) { // 如果这个格子是出口，则程序结束 if (x == 7 && y == 12) { // 当前格子设置为2 a[x][y] = 2; // 输出数组 System.out.println("迷宫有解："); showArray(); // 退出程序 System.exit(0); } else { // 当前格子设置为2，入栈 a[x][y] = 2; MyStack.push(x, y); // 按上、右、下、左顺序依次走其他格子 if (nengZou(x - 1, y)) { goMiGong(x - 1, y); } if (nengZou(x, y + 1)) { goMiGong(x, y + 1); } if (nengZou(x + 1, y)) { goMiGong(x + 1, y); } if (nengZou(x, y - 1)) { goMiGong(x, y - 1); } // 出栈（且还原为1）（栈空则无解） p = MyStack.pop(); if (p[0] == -1) { System.out.println("迷宫无解"); } else { a[p[0]][p[1]] = 1; } } } // 判断（x,y）是否可以走。判断方法： // 1、超出数组不能走；2、在栈内（为2）不能走；3、为0不能走 // 即：都大于等于0，且对应数组值为1，就可以走。 public static boolean nengZou(int x, int y) { boolean b = false; if (x >= 0 && y >= 0&&x<8&&y<13) { if (a[x][y] == 1) { b = true; } } return b; } }
辅助栈（myStack.java）
public class MyStack { public static int[][] n = new int[150][2]; public static int p = 150; public static void push(int x, int y) { p--; n[p][0] = x; n[p][1] = y; } public static int[] pop() { int[] x = new int[2]; if (p == 150)//栈空 { x[0] = -1; x[1] = -1; } else { x[0] = n[p][0]; x[1] = n[p][1]; p++; } return x; } }
程序运行结果：
人为修改最后一行第一个元素的值为0，发现并未输出正确结果。
请检查程序，修改它，得出正确的程序。
提示：判断“迷宫无解”的条件。什么情况下迷宫无解？当弹出迷宫入口的时候，即可判定无解。
原文：https://www.cnblogs.com/wanjinliu/p/13660970.html