Problema
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 = 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};
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;Explicação
O centro é uma parede. Ir duas vezes para a direita e duas vezes para baixo (ou para baixo e depois para a direita) entra em 4 células de custo 1, total 4.
Entrada:
goal = [0, 2]
grid = [
[1, 9, 1],
[1, 9, 1],
[1, 1, 1]
]
start = [0, 0]
Saída 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};
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;Explicação
Atravessar o 9 diretamente custa 9 + 1 = 10. Descer, seguir pela linha de baixo e subir de novo entra em seis células de custo 1, total 6.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Use uma priority queue ordenada por custo percorrido mais distância de Manhattan até o objetivo.
Dica 2
Guarde o melhor custo encontrado até agora para cada célula e só expanda uma célula quando esse caminho a melhorar.
Dica 3
Trate walls e células de início ou fim bloqueadas como impossíveis, e lembre que entrar na célula inicial é grátis.
Complexidade esperada
tempo O(rows * cols log(rows * cols)), espaço extra O(rows * cols)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.