MAIS OUI ! Tracer les points que j'ai déjà visité pour eviter de revenir en arriere, j'y avais pensé en plus xD
Du coup, en ayant fait à LaRache© sans opti* , ça donne ça ! je rajoute une liste de visited à chaque appel, et je verifie si la future position n'est pas déjà dedans avant de faire l'appel recursif.
Code:
public static boolean routeExistsRecur(int fromRow, int fromColumn, int toRow, int toColumn,
boolean[][] mapMatrix, List<String> visited) {
//si destination pas une route -> false
if (!mapMatrix[toRow][toColumn]) {
return false;
}
//si depart pas une route -> false
if (!mapMatrix[fromRow][fromColumn]) {
return false;
}
//si on est à destination
if (fromRow == toRow && fromColumn == toColumn) {
return mapMatrix[toRow][toColumn];
}
List<String> newVisited = new ArrayList<>(visited);
newVisited.add(fromRow +"-" + fromColumn);
//celulle à droite
if (fromColumn +1 <= toColumn && mapMatrix[fromRow][fromColumn+1] && !visited.contains(fromRow +"-" + (fromColumn+1))
&& routeExistsRecur(fromRow, fromColumn+1, toRow, toColumn, mapMatrix, newVisited)) {
return true;
}
//cellule en bas
else if (fromRow+1 <= toRow && mapMatrix[fromRow+1][fromColumn] && !visited.contains((fromRow+1) +"-" + fromColumn)
&& routeExistsRecur(fromRow+1, fromColumn, toRow, toColumn, mapMatrix, newVisited)) {
return true ;
}
//cellule à gauche
else if (fromColumn > 0 && mapMatrix[fromRow][fromColumn-1] && !visited.contains(fromRow +"-" + (fromColumn-1))
&& routeExistsRecur(fromRow, fromColumn-1, toRow, toColumn, mapMatrix, newVisited)) {
return true ;
}
//cellule en haut
else if (fromRow > 0 && mapMatrix[fromRow-1][fromColumn] && !visited.contains((fromRow-1) +"-" + fromColumn)
&& routeExistsRecur(fromRow-1, fromColumn, toRow, toColumn, mapMatrix, newVisited)) {
return true;
}
return false;
}
public static boolean routeExists(int fromRow, int fromColumn, int toRow, int toColumn,
boolean[][] mapMatrix) {
return routeExistsRecur(fromRow, fromColumn, toRow, toColumn, mapMatrix, new ArrayList<>());
}
75% , il y a le test de performance sur grosse map qui foire, sans surprise. Bon y'a du mieux. Je vais poster l'exo sur le topic programm, je suis curieux de voir les réponses des gens.
Le cas qui partez en overflow: partir de (1,0) et allez vers (0,2) en ayant mis (0,2) à true
Code:
{true, false, true(A)},
{(D)true, true, false},
{false, true, false}
*Oui je sais, c'est ultra moche , et je me suis battu un con avec les égalités de tableaux vu que ma liste de visited au départ c'etait une List<int[]>, finalement je suis parti sur des String, parce que pourquoi s'emmerder ?
Aprés avoir fait du groovy pendant 4 ans, ça pique de devoir re-manipuler des tableaux et des listes en java