Java实现迷宫最短路径的BFS算法

桃扇骨 2023-07-20 05:54 15阅读 0赞

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

利用广度优先遍历算法的特点，由于迷宫每次只能走一格，所以对于任意一个节点，bfs第一次到达该点时一定是最短路径。

package recursion;
    
    import java.util.ArrayDeque;
    import java.util.Deque;
    import java.util.Stack;
    
    public class Maze {
        
    	private class Node{
        
    		int x;
    		int y;
    		public Node(int x, int y) {
        
    			this.x = x;
    			this.y = y;
    		}
    	}
    	private int[][] map;
    	//起点
    	private int startX;
    	private int startY;
    	//终点
    	private int endX;
    	private int endY;
    	//代表上下左右四个可能走的方向
    	private int[] dx = {
        1,0,-1,0};
    	private int[] dy = {
        0,1,0,-1};
    	public Maze(int[][] map, int startX, int startY, int endX, int endY) {
        
    		this.map = map;
    		this.startX = startX;
    		this.startY = startY;
    		this.endX = endX;
    		this.endY = endY;
    	}
    	public void print(int[][] map) {
        
    		for(int i=0; i<map.length; i++) {
        
    			for(int j=0; j<map[0].length; j++) {
        
    				System.out.printf("%4d",map[i][j]);
    			}
    			System.out.println();
    		}
    	}
    	//广度优先遍历寻找迷宫所有点的最短路径， x,y是起始点
    	public void bfs() {
        
    		Deque<Node> quene = new ArrayDeque<Node>();
    		//存储每个点的前驱节点，方便打印最短路径的路线
    		int[][] pre = new  int[this.map.length][this.map[0].length];
    		//存储每个点的最短路径
    		int[][] dis = new  int[this.map.length][this.map[0].length];
    		for(int i=0; i<dis.length; i++) {
        
    			for(int j=0; j<dis[0].length; j++) {
        
    				dis[i][j] = 100;
    			}
    		}
    		//将起点入队，起点的距离设为0，并标记为已访问
    		quene.add(new Node(this.startX, this.startY));
    		dis[this.startX][this.startY] = 0;
    		map[this.startX][this.startY] = 2;
    		Node temp;
    		//广度优先遍历所有可访问的点，并记下每个点的最短路径和前驱节点
    		while(!quene.isEmpty()) {
        
    			temp = quene.poll();
    			//尝试每个点的四个方向
    			for(int i=0; i<4; i++) {
        
    				int tx = temp.x + dx[i];
    				int ty = temp.y + dy[i];
    				//如果该点没有访问过，将该点入队并标记为访问过
    				if(map[tx][ty] == 0) {
        
    					//迷宫中每次只能走一步，所以距离加一
    					dis[tx][ty] = dis[temp.x][temp.y] + 1;
    					pre[tx][ty] = i;
    					map[tx][ty] = 2;
    					quene.add(new Node(tx, ty));
    				}
    			}
    		}//到这里dis中存放的就是最短路径，下面时利用pre数组打印路径
    		
    		int a = this.endX;
    		int b = this.endY;
    		System.out.printf("从(%d,%d)到(%d,%d)的最短距离是：%d，路线为：\n",
    				this.startX, this.startY, a, b, dis[a][b]);
    		//倒序访问最短路径的路线并入栈
    		Stack<Node> stack = new Stack<Node>();
    		stack.add(new Node(a, b));
    		while(a != this.startX || b != this.startY) {
        
    			int da = dx[pre[a][b]];
    			int db = dy[pre[a][b]];
    			a = a - da;
    			b = b - db;
    			stack.add(new Node(a,b));
    		}
    		//出栈的顺序就是从起点到终点的路线
    		while(!stack.isEmpty()) {
        
    			Node p = stack.pop();
    			System.out.printf("(%d,%d)->",p.x,p.y);
    		}
    	}
    	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(map, 1, 1, 5, 5);
    		maze.bfs();
    	}
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982