首页 > 编程学习 > java迷宫寻找最短路径

java迷宫寻找最短路径

发布时间:2022/11/24 23:21:04

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

直接上代码:

package com.common.utils;import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;/*** @ClassName Calculator* @Description:  java迷宫寻找最短路径* @Author: mischen* @date: 14:57 2022/11/24* @Version 1.0*/
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 static 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<>();//存储每个点的前驱节点,方便打印最短路径的路线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<>();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) {//创建一个迷宫并初始化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;print(map);Maze maze = new Maze(map, 1, 1, 5, 2);maze.bfs();}
}

运行结果:
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 0 0 0 -1
-1 0 0 0 0 0 0 -1
-1 0 0 0 -1 0 0 -1
-1 -1 -1 0 -1 0 0 -1
-1 0 0 -1 0 0 0 -1
-1 0 0 0 0 0 0 -1
-1 -1 -1 -1 -1 -1 -1 -1
从(1,1)到(5,2)的最短距离是:13,路线为:
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(6,5)->(6,4)->(6,3)->(6,2)->(5,2)->


本文链接:https://www.ngui.cc/article/show-701462.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000