Tous les défis
Moyen 2 résolus 100.0 % de réussite

A* Search on a Weighted Grid

Find the cheapest path across a grid of terrain costs with A*, the search algorithm behind game and robot pathfinding.

Ce que vous allez apprendre

  • Find the cheapest path with a priority queue
  • Use the Manhattan distance as a heuristic
  • Understand why admissible heuristics stay optimal

Problème

Afficher la traduction

A* is the classic pathfinding algorithm of games and robotics. It explores cells in order of f = g + h, where g is the cost paid so far and h is a heuristic estimate of the cost still to go.

The grid holds a cost for every cell: entering a cell costs its value, and 0 means a wall that cannot be entered. You start on start (its cost is not paid) and may move up, down, left or right.

Use A* with the Manhattan distance |row - goal_row| + |col - goal_col| as the heuristic. Every open cell costs at least 1, so this heuristic never overestimates and A* returns an optimal answer.

Implement a_star_cost(grid, start, goal).

Input

grid: A matrix of cell costs (0 = wall).

start, goal: [row, col] positions.

Output

Return the minimum total cost to reach goal, or -1 if it cannot be reached (including when start or goal is a wall).

Contraintes

1 ≤ rows, cols ≤ 100

0 ≤ each cost ≤ 9

Exemples

Exemple 1
Entrée :
grid = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
start = [0, 0]
goal = [2, 2]

Sortie attendue :
expected = 4
Entrée :
std::vector<std::vector<long long>> grid = {
    {1, 1, 1},
    {1, 0, 1},
    {1, 1, 1}
};
std::vector<long long> start = {0, 0};
std::vector<long long> goal = {2, 2};

Sortie attendue :
long long expected = 4;
Entrée :
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};
long[] goal = new long[] {2, 2};

Sortie attendue :
long expected = 4;

Explication

The centre is a wall. Going right twice and down twice (or down then right) enters 4 cells of cost 1: total 4.

Exemple 2
Entrée :
grid = [
    [1, 9, 1],
    [1, 9, 1],
    [1, 1, 1]
]
start = [0, 0]
goal = [0, 2]

Sortie attendue :
expected = 6
Entrée :
std::vector<std::vector<long long>> grid = {
    {1, 9, 1},
    {1, 9, 1},
    {1, 1, 1}
};
std::vector<long long> start = {0, 0};
std::vector<long long> goal = {0, 2};

Sortie attendue :
long long expected = 6;
Entrée :
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};
long[] goal = new long[] {0, 2};

Sortie attendue :
long expected = 6;

Explication

Crossing the 9 directly costs 9 + 1 = 10. Going down, along the bottom row and back up enters six cells of cost 1: total 6.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Use a priority queue ordered by traveled cost plus Manhattan distance to the goal.

Indice 2

Track the best cost found so far for each cell, and only expand a cell when this path improves it.

Indice 3

Treat walls and blocked start or goal cells as impossible, and remember entering the start cell is free.

Complexité attendue

O(rows * cols log(rows * cols)) time, O(rows * cols) extra space

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 849 ms - 5/5 Voir le code
2 HTHolota Tudor Python 867 ms - 4/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 2 solutions complètes ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.