通过递归解决迷宫回溯问题（Java）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了通过递归解决迷宫回溯问题（Java），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1757字，纯文字阅读大概需要3分钟。

内容图文

问题描述：
采用递归的方式求出小球在一个迷宫中，从起始点到终点的一条路径，由于在递归的过程中，采用的策略方式不同，所得到的结果不同，这里采用了 下–右--上–左的递归方式进行求解
public class Main {
public static void main(String[] args) {
Map m=new Map();
System.out.println(“初始地图为：”);
m.show();
int[][] map=m.getMap();
boolean key=setWay(map, 1, 1, 6, 5);
if(key) {
System.out.println(“小球的路径为：”);
m.show();
}else {
System.out.println(“小球不存在路径”);
}
}
/*
* 使用递归回溯求出小球路径
* 1.map表示地图
* 2.i，表示出发点，a,b，表示终点
* 3.约定：map[i][j]=1表示为墙，走不通 为0表示没有走过 为2表示可以走 为3表示改点已经走过，走不通
* 4.在走迷宫的时候的，需要确定一个策略：递归的放向依次为 下—右---上----左
*/
public static boolean setWay(int[][] map,int i,int j,int a,int b) {
if(map[a][b]==2) {
return true;
}
if(map[i][j]==0) {
map[i][j]=2;
if(setWay(map, i+1, j, a, b)) {//向下尝试
return true;
}else if(setWay(map, i, j+1, a, b)) {//向右尝试
return true;
}else if(setWay(map, i-1, j, a, b)){//向上尝试
return true;
}else if(setWay(map, i, j-1, a, b)){//向左尝试
return true;
}else {
map[i][j]=3;
return false;
}
}else {
return false;
}
}
}

class Map{//迷宫地图
private int row=8;//行
private int col=7;//列
private static int[][] map;//表示地图的矩阵
public Map() {
map=new int[row][col];
//地图矩阵初始化
for(int i=0;i<row;i++) {
map[i][0]=1;
map[i][6]=1;
}
for(int i=0;i<col;i++) {
map[0][i]=1;
map[7][i]=1;
}
map[3][1]=1;
map[3][2]=1;
}
public static int[][] getMap(){//获取到地图矩阵
return map;
}

public void show() {//显示地图
	for(int i=0;i<row;i++) {
		for(int j=0;j<col;j++) {
			System.out.print(map[i][j]+" ");
		}
		System.out.println();
	}
}

}

结果：

总结：通过该问题的求解，对递归回溯的理解更加深刻。但次方法存在一定的缺陷，效率太低。

内容总结

以上是互联网集市为您收集整理的通过递归解决迷宫回溯问题（Java）全部内容，希望文章能够帮你解决通过递归解决迷宫回溯问题（Java）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端