欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

Java 数据结构和算法 - 递归和回溯

最编程 2024-06-29 21:20:28
...
package com.szh.recursion; /** * 走迷宫问题 */ public class MiGong { //使用递归回溯来给小球找路, 说明: //1. map 表示地图 //2. i,j 表示从地图的哪个位置开始出发 (1,1) //3. 如果小球能到 map[6][5] 位置，则说明通路找到. //4. 约定：当 map[i][j] 为 0 表示该点没有走过; 当为 1 表示墙; 2 表示通路可以走; //5. 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通，再回溯 public static boolean setWay(int[][] map, int i, int j) { //此时走到了迷宫终点 if (map[6][5] == 2) { return true; } else { if (map[i][j] == 0) { //如果当前这个点还没有走过 //按照策略 下->右->上->左 走 map[i][j] = 2; if (setWay(map, i + 1, j)) { //下 return true; } else if (setWay(map, i, j + 1)) { //右 return true; } else if (setWay(map, i - 1, j)) { //上 return true; } else { //左 return true; } } else { //map[i][j] != 0, 即只能为1、2。 1表示墙（无法走），2表示已经走过了，所以此时直接返回false return false; } } } //修改找路的策略，改成 上->右->下->左 public static boolean setWay2(int[][] map, int i, int j) { if(map[6][5] == 2) { // 通路已经找到ok return true; } else { if(map[i][j] == 0) { //如果当前这个点还没有走过 //按照策略 上->右->下->左 map[i][j] = 2; if(setWay2(map, i - 1, j)) { //上 return true; } else if (setWay2(map, i, j + 1)) { //右 return true; } else if (setWay2(map, i + 1, j)) { //下 return true; } else { //左 return true; } } else { return false; } } } public static void main(String[] args) { //先创建一个二维数组，模拟迷宫 (地图) int[][] map = new int[8][7]; //使用迷宫中的部分格子表示墙体（置1） //第一行和最后一行置为1 for (int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; } //第一列和最后一列置为1 for (int i = 0; i < 8; i++) { map[i][0] = 1; map[i][6] = 1; } //多添加两块墙体 map[3][1] = 1; map[3][2] = 1; // map[1][2] = 1; // map[2][2] = 1; //输出地图查看 System.out.println("原始迷宫地图为："); for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } //使用递归回溯走迷宫 setWay(map, 1, 1); // setWay2(map, 1, 1); System.out.println("小球走过，并标识过的地图的情况："); for (int i = 0; i < 8; i++) { for (int j = 0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } } }

上一篇： 迷宫的最短路径

下一篇： 数据结构与算法 - 递推迷宫问题

推荐阅读