Java实现迷宫回溯

雨点打透心脏的1/2处 2023-07-10 12:59 3阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][Java]

算法还是蛮有意思的，这个算法可以找到通路，但不是最优解。迷宫最短路径参考：https://blog.csdn.net/weixin\_44963741/article/details/105227749  
测试结果如下图：

![在这里插入图片描述][20200302201710426.png]  
代码如下：

public class Maze {
        
    
    	public void print(int[][] map) {
        
    		for(int i=0; i<map.length; i++) {
        
    			for(int j=0; j<map[0].length; j++) {
        
    				System.out.print(map[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}
    	/**
    	 * 地图上的1表示墙，2表示可以走通，3表示此路不通
    	 * @param map 传入地图
    	 * @param x 起点横坐标
    	 * @param y 起点纵坐标
    	 * @param a 终点横坐标
    	 * @param b 终点纵坐标
    	 */
    	public boolean start(int[][] map, int x, int y, int a, int b) {
        
    		if(map[a][b] == 2) {
        
    			print(map);
    			return true;
    		}else {
        
    			if(map[x][y] == 0) {
        
    				map[x][y] = 2;//先假设该点可以走通
    				System.out.println(x + "," + y);
    				if(start(map, x+1, y, a, b)) {
        //下
    					return true;
    				}else if(start(map, x, y+1, a, b)) {
        //右
    					return true;
    				}else if(start(map, x-1, y, a, b)) {
        //上
    					return true;
    				}else if (start(map, x, y-1, a, b)){
        //左
    					return true;
    				}else {
        
    					map[x][y] = 3;//走不通时设为3
    				}
    			}
    		}
    		return false;
    	}
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    
    		//创建一个迷宫并初始化
    		int[][] map = new int[8][8];
    		for(int i=0; i<map.length; i++) {
        
    			for(int j=0; j<map[0].length; j++) {
        
    				map[i][j] = 0;
    			}
    		}
    		for(int i=0; i<map.length; i++) {
        
    			map[i][0] = 1;
    			map[i][7] = 1;
    			map[0][i] = 1;
    			map[7][i] = 1;
    		}
    		map[4][1] = 1;
    		map[4][2] = 1;
    		map[5][3] = 1;
    		map[4][4] = 1;
    		map[3][4] = 1;
    		Maze maze = new Maze();
    		maze.start(map, 1, 1, 5, 6);
    	}
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982
[20200302201710426.png]: https://img-blog.csdnimg.cn/20200302201710426.png