Reputation: 89
I am trying to know and understand as many algorithms as I can and I stumbled across a strange algorithm in a contest packet that finds the minimum number of steps to solve a maze (shortest path). I understand it 100%, but I don't know what algorithm it is and the packet did not state the name of it. I would really like to know the name of this algorithm (if it has a name) so I can do more research on it.
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);
}
}
Upvotes: 3
Views: 1098