用Java实现迷宫最短路径算法 |
您所在的位置：网站首页 › java走迷宫最短路径 › 用Java实现迷宫最短路径算法 |
用Java实现迷宫最短路径算法
|
单源最短路（Bellman - Ford算法）
宽度优先搜索
迷宫最短路径用宽度优先搜索（bfs）相比用深度优先搜索（dfs）的好处在于bfs每次计算都是最短路径不存在重复计算，而dfs每计算出一条可行的路径都要与先前的路径比较，然后储存最短路径。 而bfs的思想是先计算出围绕起点的所有点的距离并储存起来 根据该思想为下题写一段程序 在N*M的迷宫中，计算出S到G的最短路径 ‘#’，’.’， ‘S’， 'G’分别表示墙壁、通道、起点、终点 代码如下： import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { /** 代码输入格式 第一行两个整数n,m如 2 2 下面n行，每行m个字符如 S# #G */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); String t = sc.nextLine(); char [][] map = new char [n][m]; int[] begin = new int [2]; int[] end = new int [2]; for(int i = 0; i < n; i++) { String s = sc.nextLine(); map[i] = s.toCharArray(); if(s.contains("S")) { begin[0] = i; begin[1] = s.indexOf("S"); } if(s.contains("G")) { end[0] = i; end[1] = s.indexOf("G"); } } System.out.println(bfs(map, begin, end)); } public static int bfs(char [][] map, int [] begin, int [] end) { //移动的四个方向 int[] dx = {1, 0, -1, 0}; int[] dy = {0, 1, 0, -1}; //用来储存距离到起始点最短路径的二维数组 int[][] d = new int [map.length][map[0].length]; //储存未进行处理的点 Queue que = new LinkedList(); //将所有的位置都初始化为最大 for(int i = 0; i < d.length; i++) { for(int j = 0; j < d[0].length; j++) { d[i][j] = Integer.MAX_VALUE; } } //将起始点放入队列 que.offer(begin); //将起始点最短路径设为0 d[ begin[0] ][ begin[1] ] = 0; //一直循环直到队列为空 while(!que.isEmpty()) { //取出队列中最前端的点 int [] current = que.poll(); //如果是终点则结束 if(current[0] == end[0] && current[1] == end[1]) break; //四个方向循环 for(int i = 0; i < 4; i++) { //试探 int ny = current[0] + dy[i]; int nx = current[1] + dx[i]; //判断是否可以走 if(ny >= 0 && ny < d.length && nx >= 0 && nx < d[0].length && map[ny][nx] != '#' && d[ny][nx] == Integer.MAX_VALUE) { //如果可以走，则将该点的距离加1 d[ny][nx] = d[current[0]][current[1]] + 1; //并将该点放入队列等待下次处理 int[] c = {ny, nx}; que.offer(c); } } } return d[end[0]][end[1]]; } } |
S是起点，数字为该点到S的距离
【本文地址】
今日新闻 |
推荐新闻 |