哈喽，小伙伴们，大家好！我是槿凉。哎呀，这几天刚学算法学的脑阔疼，这不今天刚学完迷宫回溯问题，连夜肝出了这篇博客，下面就跟小伙伴们分享一下我的学习成果叭！
如何理解"回溯"这个词呢？说白了就是利用递归相关的知识，来解决一些实际生活中的问题。这里我用一个简单的迷宫游戏带大家理解一下这个算法！
话不多说，先上代码：
publicclassmigong { publicstaticvoidmain(String[] args) { // TODO 自动生成的方法存根//地图int [][] map=newint[10][10]; //使用1表示墙//上下全部置为1for(inti=0;i<10;i++) { map[0][i] =1; map[9][i] =1; } //左右全部置为1for(inti=0;i<10;i++) { map[i][0] =1; map[i][9] =1; } //设置挡板map[3][1] =1; map[3][2] =1; map[4][3] =1; map[5][4] =1; map[6][5] =1; map[7][6] =1; map[8][7] =1; // 输出地图for(inti=0;i<10;i++) { for(intj=0;j<10;j++) { System.out.print(map[i][j]+" "); } System.out.println(); }
这个代码段就是我们先要设计一个迷宫地图出来，这里我们利用二维数组来处理这个问题，我们定义一个10*10的二维数组，我们将1视为墙，利用for循环遍历给数组赋值，然后可以设计出我们想要的迷宫，下面来看运行结果。
好了，迷宫我们已经设计好了，接下来我们要让小球按照我们规定的路线来找到出口，这里我们需要给出小球的初始位置，已经我们想让小球到达的终点位置，看代码：
setWay(map,1,1);//小球起始位置System.out.println("小球走过，并标识过的地图情况"); for(inti=0;i<10;i++) { for(intj=0;j<10;j++) { System.out.print(map[i][j]+" "); } System.out.println(); } } publicstaticbooleansetWay(int[][]map,inti ,intj){ if(map[8][8]==2) {//通路已经找到okreturntrue; } else { if(map[i][j]==0) {//如果当前这个点还没有走过map[i][j]=2;//假定该点可以走通if(setWay(map,i+1,j)) {//向下走returntrue; }elseif(setWay(map,i,j+1)) {//向右走returntrue; } elseif(setWay(map,i,j-1)) {//向左走returntrue; } elseif(setWay(map,i-1,j)) {//向上走returntrue; }else { map[i][j]=3;//说明该点走不通，是死路returnfalse; } }else {//如果map[i][j]！=0,可能是1,2,3returnfalse; } } } }
大家可以详细看一下代码段的内容，每一个部分都注释的非常清楚，该问题最关键的是要确定小球的行走路线，这里我们需要确定一个策略（方法)，根据下->右->左->上来让小球行走，如果该点走不通，再回溯，最后大家看一下最终的运行结果：
其中红线标注的是小球的具体行走路线，可以看到小球是按照我们的想法"下->右->左->上"，来行走的，这说明我们的方法是可行的。
下面给出完整的代码，大家有兴趣的可以在自己的电脑上面运行一下玩一玩，没有装java编译器的小伙伴没有关系，大家可以在百度搜索java在线工具-->菜鸟工具-->选择java语言就可以在线运行了：
publicclassmigong { publicstaticvoidmain(String[] args) { // TODO 自动生成的方法存根//地图int [][] map=newint[10][10]; //使用1表示墙//上下全部置为1for(inti=0;i<10;i++) { map[0][i] =1; map[9][i] =1; } //左右全部置为1for(inti=0;i<10;i++) { map[i][0] =1; map[i][9] =1; } //设置挡板map[3][1] =1; map[3][2] =1; map[4][3] =1; map[5][4] =1; map[6][5] =1; map[7][6] =1; map[8][7] =1; // 输出地图for(inti=0;i<10;i++) { for(intj=0;j<10;j++) { System.out.print(map[i][j]+" "); } System.out.println(); } setWay(map,1,1);//小球起始位置System.out.println("小球走过，并标识过的地图情况"); for(inti=0;i<10;i++) { for(intj=0;j<10;j++) { System.out.print(map[i][j]+" "); } System.out.println(); } } //1.使用递归回溯来给小球找路/*2.map 表示地图*3. i 从哪个位置开始找(1,1)*4.如果小球找到map[6][5],表示通路已经找到*约定：当map[i][j]为0表示该点没有走过，当为1表示墙，2表示通路可以走，3表示该点已经走过，但是走不通*在走迷宫时，需要确定一个策略（方法)，下->右->左->上，如果该点走不通，在回溯*5. 如果找到通路，就返回true,否则返回false* */publicstaticbooleansetWay(int[][]map,inti ,intj){ if(map[8][8]==2) {//通路已经找到okreturntrue; } else { if(map[i][j]==0) {//如果当前这个点还没有走过map[i][j]=2;//假定该点可以走通if(setWay(map,i+1,j)) {//向下走returntrue; }elseif(setWay(map,i,j+1)) {//向右走returntrue; } elseif(setWay(map,i,j-1)) {//向左走returntrue; } elseif(setWay(map,i-1,j)) {//向上走returntrue; }else { map[i][j]=3;//说明该点走不通，是死路returnfalse; } }else {//如果map[i][j]！=0,可能是1,2,3returnfalse; } } } }
运行结果：
