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);
    }
}
有帮助吗?

解决方案

Breadth-first search with backtracking.

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top