Ich bin dabei ein Labyrinth Rekursiv zu durchsuchen. Klappt auch bei kleinen Labyrinthen.
Code ist folgender, sollte eigentlich selbsterklärend sein denk ich. Problem ist nun folgendes. Der Professor hat viele JUnit Tests geschrieben und bei großen Labyrinthen dauert es zu lang (4s) und bricht daher ab. Wie schreibe ich den Code Performanter? Oder hab ich einen Denkfehler im Code?
Sprache natürlich Java
Ich kann nicht ausschließen, dass die Tests nicht dazu da sind zu erkennen wie performant der Code generell ist. Heißt, dass man guckt wie viele Tests er schafft um zu wissen welche Performance klasse man so etwa hat.
Stack<Coordinate> shortestPath;
private void recursivelyDiscoveryMaze(int x, int y, int depth, Stack<Coordinate> currentPath) {
//this.maze.prettyPrint();
currentPath.push(new Coordinate(x, y));
if (dX == x && dY == y) {
if (shortestPath.size() > currentPath.size() || shortestPath.size() == 0) {
shortestPath = (Stack<Coordinate>) currentPath.clone();
}
currentPath.pop();
return;
}
this.maze.getMazeField()[x][y] = 1; //set visited
depth++;
if (isValidStep(x + 1, y)) //if can be visited
recursivelyDiscoveryMaze(x + 1, y, depth, currentPath);
if (isValidStep(x, y + 1))
recursivelyDiscoveryMaze(x, y + 1, depth, currentPath);
if (isValidStep(x - 1, y))
recursivelyDiscoveryMaze(x - 1, y, depth, currentPath);
if (isValidStep(x, y - 1))
recursivelyDiscoveryMaze(x, y - 1, depth, currentPath);
depth--;
this.maze.getMazeField()[x][y] = 0; //set unvisited
currentPath.pop();
}
