我试图尽可能多地了解和理解算法,我偶然发现了一个竞赛数据包中的一个奇怪算法,该数据包找到了解决迷宫的最小步骤(最短路径).我100%理解它,但是我不知道它是什么算法,数据包没有说明它的名称.我真的很想知道该算法的名称(如果有名称的话),因此我可以对其进行更多的研究.
import java.io.File;
import java.util.Scanner;
class spot {
char type;
int distance;
spot closest;
public spot() {
type = '.';
distance = Integer.MAX_VALUE;
closest = null;
}
}
public class myalg {
public static void main(String args[]) throws Exception {
int moves = 0;
Scanner keyb = new Scanner(new File("src/mar2014/maze2.txt"));
int rows = keyb.nextInt();
int cols = keyb.nextInt();
spot mat[][] = new spot[rows][cols];
keyb.nextLine();
spot startSpot = null;
spot endSpot = null;
for (int i = 0; i < mat.length; i++) {
String line = keyb.nextLine();
for (int j = 0; j < mat[i].length; j++) {
mat[i][j] = new spot();
mat[i][j].type = line.charAt(j);
if (mat[i][j].type == 'S') {
startSpot = mat[i][j];
startSpot.distance = 0;
startSpot.type = ' ';
}
if (mat[i][j].type == 'E') {
endSpot = mat[i][j];
endSpot.type = ' ';
}
}
}
boolean changeMade = true;
while (changeMade) {
changeMade = false;
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[i].length; j++) {
spot thisSpot = mat[i][j];
spot adjacentSpots[] = {null, null, null, null};
if (i > 0) {
adjacentSpots[0] = mat[i - 1][j];
}
if (i < cols - 1) {
adjacentSpots[1] = mat[i + 1][j];
}
if (j > 0) {
adjacentSpots[2] = mat[i][j - 1];
}
if (j < rows - 1) {
adjacentSpots[3] = mat[i][j + 1];
}
if (thisSpot.type == ' ') {
for (int k = 0; k < 4; k++) {
if (adjacentSpots[k] != null && adjacentSpots[k].distance < (thisSpot.distance - 1)) {
thisSpot.distance = adjacentSpots[k].distance + 1;
thisSpot.closest = adjacentSpots[k];
changeMade = true;
}
}
}
}
}
}
spot spot = endSpot;
while(spot != startSpot) {
moves++;
spot.type = '.';
spot = spot.closest;
}
System.out.println(moves);
}
}
解决方法:
具有回溯功能的广度优先搜索.