剑指Offer——回溯算法解迷宫问题（java版）
以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计程序，对任意设定的迷宫，求出从入口到出口的所有通路。
下面我们来详细讲一下迷宫问题的回溯算法。
(入口) 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(出口)
该图是一个迷宫的图。1代表是墙不能走，0是可以走的路线。只能往上下左右走，直到从左上角到右下角出口。
做法是用一个二维数组来定义迷宫的初始状态，然后从左上角开始，不停的去试探所有可行的路线，碰到1就结束本次路径，然后探索其他的方向，当然我们要标记一下已经走的路线，不能反复的在两个可行的格子之间来回走。直到走到出口为止，算找到了一个正确路径。
程序如下，具体做法看注释即可。
package cn.edu.ujn.demo;
/**
* @author SHQ
*
* 迷宫问题求解
*
* 思路
* 递归+回溯
*
* 按照右-->左-->下-->上的顺序寻路，已走过的路径用5标志
*
*
*/
public class MiGong {
public static void main(String[] args) {
int maxRow,maxLine,p;
Scanner in = new Scanner(System.in);
Pattern pattern = Pattern.compile("[ ]+");
String s = in.nextLine();
String [] str = pattern.split(s);
// 获取行
maxRow = Integer.parseInt(str[0]);
// 获取列
maxLine = Integer.parseInt(str[1]);
// 获取能量值
// p = Integer.parseInt(str[2]);
int [][] array = new int [maxRow][maxLine];
for(int i = 0; i < maxRow; i++){
for(int j = 0; j < maxLine; j++){
array[i][j] = in.nextInt();
}
}
Long start = System.currentTimeMillis();
new MiGong().check(0, 0, array, maxRow, maxLine);
Long end = System.currentTimeMillis();
System.out.println("耗时：" + (end-start) + "ms");
}
/**
* 制定走的规则
* @param i
* @param j
* @param array
* @param maxRow
* @param maxLine
*/
private void check(int i, int j, int[][] array, int maxRow, int maxLine) {
// 递归出口(如果到达右下角出口)
if (i == maxRow - 1 && j == maxLine - 1) {
print(array, maxRow, maxLine);
return;
}
//向右走
if (canMove(i, j, i, j + 1, array, maxRow, maxLine)) {
// 已走过的点置标志位5
array[i][j] = 5;
// 从下一个点继续寻路
check(i, j + 1, array, maxRow, maxLine);
// 均不可行，则恢复现场
array[i][j] = 0;
}
//向左走
if (canMove(i, j, i, j - 1, array, maxRow, maxLine)) {
// 标记为已走
array[i][j] = 5;
// 递归调用
check(i, j - 1, array, maxRow, maxLine);
array[i][j] = 0;
}
//向下走
if (canMove(i, j, i + 1, j, array, maxRow, maxLine)) {
array[i][j] = 5;
check(i + 1, j, array, maxRow, maxLine);
array[i][j] = 0;
}
//向上走
if (canMove(i, j, i - 1, j, array, maxRow, maxLine)) {
array[i][j] = 5;
check(i - 1, j, array,maxRow, maxLine);
array[i][j] = 0;
}
}
/**
* 判断[i,j]-->[targetI,targetJ]是否可行
* @param i
* @param j
* @param targetI
* @param targetJ
* @param array
* @param maxRow
* @param maxLine
* @return boolean 可否通过
*/
private boolean canMove(int i, int j, int targetI, int targetJ, int[][] array, int maxRow, int maxLine) {
// 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;
}
/**
* 打印可行路径
* @param array
* @param maxRow
* @param maxLine
*/
private void print(int [][] array, int maxRow, int maxLine) {
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();
}
}
} 计算结果如下：