数据结构之利用递归算法解决迷宫问题

迷宫问题：就是将一个小球放置在一个位置，通过一定的策略找到出口，在本篇中制定的策略只是其中一种，如果有兴趣，可以修改策略，来玩一玩，其实也会牵扯到另一个问题就是可以制定不同的策略，所有的距离长度是不一样的，可以将这些策略做一个统计，获取迷宫问题的最短路径

，下面就直接代码了

迷宫的样式可以自己设定

package com.gcy.recursion;
/**
* 使用递归解决迷宫问题
* @author Administrator
*
*/
public class MiGong {

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;
}
//左右
for(int i=0;i<8;i++) {
map[i][0]=1;
map[i][6]=1;
}
//进去的两个,设置挡板
map[3][1]=1;
map[3][2]=1;

//遍历map
//地图情况
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);
//输出新的地图，表示小球走过并标识过的
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(" ");
}
}
/**
* 使用递归方式给小球找路
* 说明：
* 开始位置map[1][1],到达位置map[6][5]
* 当map[i][j]=0时，表示该点小球还没有走过，当为1的时候表示墙，当为2的时候表示可以走，当为3时，表示该位置已经走过，但是走不通
* 制定策略，在走迷宫时，依次是下——>右——>上——>左，如果走不通在回溯
*
* @param map 地图
* @param i 从哪个位置开始找(行)
* @param j 从哪个位置开始找(列)
* @return 如果找到返回true
*/
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 {//如果上面条件都不满足，则证明这个点是个死路，要设置为3
map[i][j]=3;
return false;
}
}else {//如果map[j][j]!=0,则有可能为1,2,3
return false;

}


}

}

}

以上就是通过下——>右——>上——>左策略来解决迷宫问题的

执行的结果图，数字2代表的就是小球出迷宫的一种路线