Problème
A* est l'algorithme de recherche de chemin classique des jeux et de la robotique. Il explore les cases dans l'ordre de f = g + h, où g est le coût déjà payé et h une estimation heuristique du coût restant.
La grille contient un coût pour chaque case : entrer dans une case coûte sa valeur, et 0 est un mur dans lequel on ne peut pas entrer. Vous partez de start (son coût n'est pas payé) et pouvez vous déplacer vers le haut, le bas, la gauche ou la droite.
Utilisez A* avec la distance de Manhattan |row - goal_row| + |col - goal_col| comme heuristique. Chaque case ouverte coûte au moins 1, donc cette heuristique ne surestime jamais et A* renvoie une réponse optimale.
Implémentez a_star_cost(grid, start, goal).
Entrée
grid : Une matrice de coûts des cases (0 = mur).
start, goal : Des positions [row, col].
Sortie
Renvoyez le coût total minimal pour atteindre goal, ou -1 s'il est inaccessible (y compris quand start ou goal est un mur).
Contraintes
1 ≤ lignes, colonnes ≤ 100
0 ≤ chaque coût ≤ 9
Exemples
Entrée :
goal = [2, 2]
grid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
start = [0, 0]
Sortie attendue :
expected = 4Entrée :
std::vector<long long> goal = {2, 2};
std::vector<std::vector<long long>> grid = {
{1, 1, 1},
{1, 0, 1},
{1, 1, 1}
};
std::vector<long long> start = {0, 0};
Sortie attendue :
long long expected = 4;Entrée :
long[] goal = new long[] {2, 2};
long[][] grid = new long[][] {
new long[] {1, 1, 1},
new long[] {1, 0, 1},
new long[] {1, 1, 1}
};
long[] start = new long[] {0, 0};
Sortie attendue :
long expected = 4;Explication
Le centre est un mur. Aller deux fois à droite puis deux fois en bas (ou en bas puis à droite) fait entrer dans 4 cases de coût 1 : total 4.
Entrée :
goal = [0, 2]
grid = [
[1, 9, 1],
[1, 9, 1],
[1, 1, 1]
]
start = [0, 0]
Sortie attendue :
expected = 6Entrée :
std::vector<long long> goal = {0, 2};
std::vector<std::vector<long long>> grid = {
{1, 9, 1},
{1, 9, 1},
{1, 1, 1}
};
std::vector<long long> start = {0, 0};
Sortie attendue :
long long expected = 6;Entrée :
long[] goal = new long[] {0, 2};
long[][] grid = new long[][] {
new long[] {1, 9, 1},
new long[] {1, 9, 1},
new long[] {1, 1, 1}
};
long[] start = new long[] {0, 0};
Sortie attendue :
long expected = 6;Explication
Traverser directement le 9 coûte 9 + 1 = 10. Descendre, longer la dernière ligne puis remonter fait entrer dans six cases de coût 1 : total 6.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Utilise une file de priorité ordonnée par le coût parcouru plus la distance de Manhattan jusqu’à la cible.
Indice 2
Garde la meilleure cost trouvée jusqu’ici pour chaque case, et n’étends une case que si ce chemin l’améliore.
Indice 3
Considère les murs et les cellules de départ ou d’arrivée bloquées comme impossibles, et rappelle-toi qu’entrer dans la case de départ est gratuit.
Complexité attendue
temps O(rows * cols log(rows * cols)), espace supplémentaire O(rows * cols)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.