Problema
A* è il classico algoritmo di ricerca del percorso in giochi e robotica. Esplora le celle in ordine di f = g + h, dove g è il costo già pagato e h è una stima euristica del costo ancora da pagare.
La griglia contiene un costo per ogni cella: entrare in una cella costa il suo valore, e 0 è un muro in cui non si può entrare. Parti da start (il suo costo non si paga) e puoi muoverti in alto, in basso, a sinistra o a destra.
Usa A* con la distanza di Manhattan |row - goal_row| + |col - goal_col| come euristica. Ogni cella aperta costa almeno 1, quindi questa euristica non sovrastima mai e A* restituisce una risposta ottima.
Implementa a_star_cost(grid, start, goal).
Input
grid: Una matrice dei costi delle celle (0 = muro).
start, goal: Posizioni [row, col].
Output
Restituisci il costo totale minimo per raggiungere goal, oppure -1 se non è raggiungibile (anche quando start o goal è un muro).
Vincoli
1 ≤ righe, colonne ≤ 100
0 ≤ ogni costo ≤ 9
Esempi
Input:
goal = [2, 2]
grid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
start = [0, 0]
Output atteso:
expected = 4Input:
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};
Output atteso:
long long expected = 4;Input:
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};
Output atteso:
long expected = 4;Spiegazione
Il centro è un muro. Andare due volte a destra e due volte in basso (o in basso e poi a destra) entra in 4 celle di costo 1, totale 4.
Input:
goal = [0, 2]
grid = [
[1, 9, 1],
[1, 9, 1],
[1, 1, 1]
]
start = [0, 0]
Output atteso:
expected = 6Input:
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};
Output atteso:
long long expected = 6;Input:
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};
Output atteso:
long expected = 6;Spiegazione
Attraversare direttamente il 9 costa 9 + 1 = 10. Scendere, percorrere la riga in basso e risalire entra in sei celle di costo 1, totale 6.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Usa una priority queue ordinata per costo percorso più distanza Manhattan dal goal.
Suggerimento 2
Tieni traccia del miglior costo trovato finora per ogni cella e espandi una cella solo quando questo path la migliora.
Suggerimento 3
Tratta muri e celle di start o goal bloccate come impossibili, e ricorda che entrare nella cella di start è gratis.
Complessità attesa
tempo O(rows * cols log(rows * cols)), spazio aggiuntivo O(rows * cols)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.