Busca A* em uma grade ponderada

A* é o algoritmo clássico de busca de caminhos em jogos e robótica. Ele explora as células em ordem de f = g + h, onde g é o custo pago até agora e h é uma estimativa heurística do custo que falta.

A grade guarda um custo para cada célula: entrar em uma célula custa o seu valor, e 0 é uma parede onde não se pode entrar. Você começa em start (o custo dela não é pago) e pode se mover para cima, para baixo, para a esquerda ou para a direita.

Use A* com a distância de Manhattan |row - goal_row| + |col - goal_col| como heurística. Toda célula aberta custa pelo menos 1, então essa heurística nunca superestima e o A* retorna uma resposta ótima.

Implemente a_star_cost(grid, start, goal).

Entrada

grid: Uma matriz de custos das células (0 = parede).

start, goal: Posições [row, col].

Saída

Retorne o custo total mínimo para chegar a goal, ou -1 se não for possível chegar (inclusive quando start ou goal é uma parede).

Restrições

1 ≤ linhas, colunas ≤ 100

0 ≤ cada custo ≤ 9

Exemplos

Entrada:
goal = [2, 2]
grid = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
start = [0, 0]

Saída esperada:
expected = 4

Entrada:
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};

Saída 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};

Saída esperada:
long expected = 4;

Entrada:
goal = [0, 2]
grid = [
    [1, 9, 1],
    [1, 9, 1],
    [1, 1, 1]
]
start = [0, 0]

Saída esperada:
expected = 6

Entrada:
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};

Saída 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};

Saída esperada:
long expected = 6;

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

• Red Blob Games, Introduction to the A* Algorithm
• Russell and Norvig, Artificial Intelligence: A Modern Approach