Problema
A* es el algoritmo clásico de búsqueda de caminos en juegos y robótica. Explora las celdas en orden de f = g + h, donde g es el coste pagado hasta ahora y h es una estimación heurística del coste que falta.
La cuadrícula guarda un coste para cada celda: entrar en una celda cuesta su valor, y 0 es un muro en el que no se puede entrar. Empiezas en start (su coste no se paga) y puedes moverte arriba, abajo, a la izquierda o a la derecha.
Usa A* con la distancia Manhattan |row - goal_row| + |col - goal_col| como heurística. Cada celda abierta cuesta al menos 1, así que esta heurística nunca sobreestima y A* devuelve una respuesta óptima.
Implementa a_star_cost(grid, start, goal).
Entrada
grid: Una matriz de costes de celdas (0 = muro).
start, goal: Posiciones [row, col].
Salida
Devuelve el coste total mínimo para llegar a goal, o -1 si no se puede alcanzar (también cuando start o goal es un muro).
Restricciones
1 ≤ filas, columnas ≤ 100
0 ≤ cada coste ≤ 9
Ejemplos
Entrada:
goal = [2, 2]
grid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
start = [0, 0]
Salida esperada:
expected = 4Entrada:
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};
Salida esperada:
long long expected = 4;Entrada:
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};
Salida esperada:
long expected = 4;Explicación
El centro es un muro. Ir dos veces a la derecha y dos veces abajo (o abajo y luego a la derecha) entra en 4 celdas de coste 1, total 4.
Entrada:
goal = [0, 2]
grid = [
[1, 9, 1],
[1, 9, 1],
[1, 1, 1]
]
start = [0, 0]
Salida esperada:
expected = 6Entrada:
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};
Salida esperada:
long long expected = 6;Entrada:
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};
Salida esperada:
long expected = 6;Explicación
Cruzar el 9 directamente cuesta 9 + 1 = 10. Bajar, recorrer la fila inferior y volver a subir entra en seis celdas de coste 1, total 6.
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.