剑指Offer——回溯算法解迷宫问题（java版）
【摘要】 剑指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...
剑指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(); } }
}
计算结果如下：
美文美图
文章来源: shq5785.blog.csdn.net，作者：No Silver Bullet，版权归原作者所有，如需转载，请联系作者。
原文链接：shq5785.blog.csdn.net/article/details/52599850
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论（0）