以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计程序，对随意设定的迷宫，求出从入口到出口的全部通路。

    以下我们来具体讲一下迷宫问题的回溯算法。

    该图是一个迷宫的图。1代表是墙不能走，0是能够走的路线。仅仅能往上下左右走。直到从左上角到右下角出口。

    做法是用一个二维数组来定义迷宫的初始状态，然后从左上角開始。不停的去试探全部可行的路线，碰到1就结束本次路径。然后探索其它的方向，当然我们要标记一下已经走的路线。不能重复的在两个可行的格子之间来回走。直到走到出口为止。算找到了一个正确路径。

    程序例如以下，详细做法看凝视就可以。

package huisu;/** * Created by wolf on 2016/3/21. */public class MiGong {    /**     * 定义迷宫数组     */    private int[][] array = {            {0, 0, 1, 0, 0, 0, 1, 0},            {0, 0, 1, 0, 0, 0, 1, 0},            {0, 0, 1, 0, 1, 1, 0, 1},            {0, 1, 1, 1, 0, 0, 1, 0},            {0, 0, 0, 1, 0, 0, 0, 0},            {0, 1, 0, 0, 0, 1, 0, 1},            {0, 1, 1, 1, 1, 0, 0, 1},            {1, 1, 0, 0, 0, 1, 0, 1},            {1, 1, 0, 0, 0, 0, 0, 0}    };    private int maxLine = 8;    private int maxRow = 9;    public static void main(String[] args) {        System.out.println(System.currentTimeMillis());        new MiGong().check(0, 0);        System.out.println(System.currentTimeMillis());    }    private void check(int i, int j) {        //假设到达右下角出口        if (i == maxRow - 1 && j == maxLine - 1) {            print();            return;        }        //向右走        if (canMove(i, j, i, j + 1)) {            array[i][j] = 5;            check(i, j + 1);            array[i][j] = 0;        }        //向左走        if (canMove(i, j, i, j - 1)) {            array[i][j] = 5;            check(i, j - 1);            array[i][j] = 0;        }        //向下走        if (canMove(i, j, i + 1, j)) {            array[i][j] = 5;            check(i + 1, j);            array[i][j] = 0;        }        //向上走        if (canMove(i, j, i - 1, j)) {            array[i][j] = 5;            check(i - 1, j);            array[i][j] = 0;        }    }    private boolean canMove(int i, int j, int targetI, int targetJ) {//        System.out.println("从第" + (i + 1) + "行第" + (j + 1) + "列。走到第" + (targetI + 1) + "行第" + (targetJ + 1) + "列");        if (targetI < 0 || targetJ < 0 || targetI >= maxRow || targetJ >= maxLine) {//            System.out.println("到达最左边或最右边，失败了");            return false;        }        if (array[targetI][targetJ] == 1) {//            System.out.println("目标是墙，失败了");            return false;        }        //避免在两个空格间来回走        if (array[targetI][targetJ] == 5) {//            System.out.println("来回走。失败了");            return false;        }        return true;    }    private void print() {        System.out.println("得到一个解：");        for (int i = 0; i < maxRow; i++) {            for (int j = 0; j < maxLine; j++) {                System.out.print(array[i][j] + " ");            }            System.out.println();        }    }}

    我把打印每一步路径推断的地方凝视掉了，放开凝视就能看到全部走的路径。

    程序运行效率是很快，基本上是在3ms之内得到全部路径。

    原本仅仅看图时我还以为仅仅有3条路径，没想到程序打出来了8条。

后来细致看看。果然是有8条路径……

    打印结果例如以下，5是用来标记路径的：

1458551044499得到一个解：5 5 1 0 0 0 1 0 5 5 1 0 0 0 1 0 5 0 1 0 1 1 0 1 5 1 1 1 0 0 1 0 5 5 5 1 5 5 5 0 0 1 5 5 5 1 5 1 0 1 1 1 1 0 5 1 1 1 0 0 0 1 5 1 1 1 0 0 0 0 5 0 得到一个解：5 5 1 0 0 0 1 0 5 5 1 0 0 0 1 0 5 0 1 0 1 1 0 1 5 1 1 1 5 5 1 0 5 5 5 1 5 5 5 0 0 1 5 5 5 1 5 1 0 1 1 1 1 0 5 1 1 1 0 0 0 1 5 1 1 1 0 0 0 0 5 0 得到一个解：5 5 1 0 0 0 1 0 0 5 1 0 0 0 1 0 5 5 1 0 1 1 0 1 5 1 1 1 0 0 1 0 5 5 5 1 5 5 5 0 0 1 5 5 5 1 5 1 0 1 1 1 1 0 5 1 1 1 0 0 0 1 5 1 1 1 0 0 0 0 5 0 得到一个解：5 5 1 0 0 0 1 0 0 5 1 0 0 0 1 0 5 5 1 0 1 1 0 1 5 1 1 1 5 5 1 0 5 5 5 1 5 5 5 0 0 1 5 5 5 1 5 1 0 1 1 1 1 0 5 1 1 1 0 0 0 1 5 1 1 1 0 0 0 0 5 0 得到一个解：5 0 1 0 0 0 1 0 5 5 1 0 0 0 1 0 5 5 1 0 1 1 0 1 5 1 1 1 0 0 1 0 5 5 5 1 5 5 5 0 0 1 5 5 5 1 5 1 0 1 1 1 1 0 5 1 1 1 0 0 0 1 5 1 1 1 0 0 0 0 5 0 得到一个解：5 0 1 0 0 0 1 0 5 5 1 0 0 0 1 0 5 5 1 0 1 1 0 1 5 1 1 1 5 5 1 0 5 5 5 1 5 5 5 0 0 1 5 5 5 1 5 1 0 1 1 1 1 0 5 1 1 1 0 0 0 1 5 1 1 1 0 0 0 0 5 0 得到一个解：5 0 1 0 0 0 1 0 5 0 1 0 0 0 1 0 5 0 1 0 1 1 0 1 5 1 1 1 0 0 1 0 5 5 5 1 5 5 5 0 0 1 5 5 5 1 5 1 0 1 1 1 1 0 5 1 1 1 0 0 0 1 5 1 1 1 0 0 0 0 5 0 得到一个解：5 0 1 0 0 0 1 0 5 0 1 0 0 0 1 0 5 0 1 0 1 1 0 1 5 1 1 1 5 5 1 0 5 5 5 1 5 5 5 0 0 1 5 5 5 1 5 1 0 1 1 1 1 0 5 1 1 1 0 0 0 1 5 1 1 1 0 0 0 0 5 0 1458551044503