亲宝软件园·资讯

展开

Java数据结构 递归之迷宫回溯 Java数据结构 递归之迷宫回溯案例讲解

去吧猫头夜鹰 人气:0
想了解Java数据结构 递归之迷宫回溯案例讲解的相关内容吗,去吧猫头夜鹰在本文为您仔细讲解Java数据结构 递归之迷宫回溯的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java数据结构,Java数据结构,递归之迷宫回溯,下面大家一起来学习吧。

问题介绍:

用二维数组表示一个迷宫,设置迷宫起点和终点,输出迷宫中的一条通路

实现思路:

二维数组表示迷宫:

0表示路且未走过、1表示墙、2表示通路,3表示已经走过但走不通

设置寻路方法setWay,传入地图和坐标参数

默认方向策略:下、右、上、左

假定传入的店没有走过且可以走通,将其值置为2,然后向下寻路,也就是将坐标 (i + 1, j) 传入寻路方法中

进行递归寻路,向下移动后,再次按照方向策略进行寻路,即再向下寻路,直到遇到死路,即下右左均走不通(因为将走过的路置为2,故向上也走不通,即遇到死路时回头不算通路),则将该点置为3,并返回false,回到上一个递归,找寻方向策略中剩下的方向,实现回溯

代码实现:

public class Maze {
	public static void main(String[] args) {
		maze();
	}
	//迷宫回溯问题
	public static void maze() {
		//创建二维数组模拟迷宫
		//使用1表示墙,0表示路
		int[][] map = new int[][]{
				{1, 1, 1, 1, 1, 1, 1},
				{1, 0, 0, 0, 0, 0, 1},
				{1, 0, 1, 0, 0, 0, 1},
				{1, 0, 1, 0, 1, 1, 1},
				{1, 1, 0, 0, 0, 0, 1},
				{1, 0, 1, 1, 0, 1, 1},
				{1, 0, 0, 0, 0, 0, 1},
				{1, 1, 1, 1, 1, 1, 1}
		};
		//输出地图
		System.out.println("迷宫:");
		for (int[] row : map) {
			for (int i : row) {
				System.out.printf("%d\t", i);
			}
			System.out.println();
		}
		System.out.println("寻路结果:");
		//开始寻路
		setWay(map, 1, 1);
		//输出地图
		for (int[] row : map) {
			for (int i : row) {
				System.out.printf("%d\t", i);
			}
			System.out.println("");
		}
 
	}
 
	//传入地图map
	//传入开始位置(i, j)
	//如果能到达右下角(6, 5),则说明找到通路
	//0表示未走过,1表示墙,2表示可以走的通路,3表示已经走过,但是走不通
	//确定方向策略:下 -> 右 -> 上 -> 左
	//若该点走不通,则回溯
	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 if (setWay(map, i, j - 1)) {
					//向左走
					return true;
				} else {
					//该点走不通
					map[i][j] = 3;
					return false;
				}
			} else {
				//如果map[i][j] != 0
				//可能是1、2、3
				return false;
			}
		}
	}
}

输出结果:

迷宫:
1	1	1	1	1	1	1	
1	0	0	0	0	0	1	
1	0	1	0	0	0	1	
1	0	1	0	1	1	1	
1	1	0	0	0	0	1	
1	0	1	1	0	1	1	
1	0	0	0	0	0	1	
1	1	1	1	1	1	1	
寻路结果:
1	1	1	1	1	1	1	
1	2	2	2	0	0	1	
1	3	1	2	0	0	1	
1	3	1	2	1	1	1	
1	1	0	2	2	0	1	
1	0	1	1	2	1	1	
1	0	0	0	2	2	1	
1	1	1	1	1	1	1	

加载全部内容

相关教程
猜你喜欢
用户评论