Problem
A* ist der klassische Wegfindungsalgorithmus in Spielen und Robotik. Er untersucht Zellen in der Reihenfolge von f = g + h, wobei g die bisher bezahlten Kosten sind und h eine heuristische Schätzung der noch verbleibenden Kosten.
Das Gitter enthält Kosten für jede Zelle: Das Betreten einer Zelle kostet ihren Wert, und 0 ist eine Wand, die nicht betreten werden kann. Du startest auf start (dessen Kosten werden nicht bezahlt) und darfst dich nach oben, unten, links oder rechts bewegen.
Verwende A* mit der Manhattan-Distanz |row - goal_row| + |col - goal_col| als Heuristik. Jede offene Zelle kostet mindestens 1, also überschätzt diese Heuristik nie und A* liefert eine optimale Antwort.
Implementiere a_star_cost(grid, start, goal).
Eingabe
grid: Eine Matrix der Zellkosten (0 = Wand).
start, goal: Positionen als [row, col].
Ausgabe
Gib die minimalen Gesamtkosten bis goal zurück, oder -1, wenn das Ziel nicht erreichbar ist (auch wenn start oder goal eine Wand ist).
Einschränkungen
1 ≤ Zeilen, Spalten ≤ 100
0 ≤ jede Kosten ≤ 9
Beispiele
Eingabe:
goal = [2, 2]
grid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
start = [0, 0]
Erwartete Ausgabe:
expected = 4Eingabe:
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};
Erwartete Ausgabe:
long long expected = 4;Eingabe:
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};
Erwartete Ausgabe:
long expected = 4;Erläuterung
Die Mitte ist eine Wand. Zweimal nach rechts und zweimal nach unten (oder erst nach unten, dann nach rechts) betritt 4 Zellen mit Kosten 1, insgesamt 4.
Eingabe:
goal = [0, 2]
grid = [
[1, 9, 1],
[1, 9, 1],
[1, 1, 1]
]
start = [0, 0]
Erwartete Ausgabe:
expected = 6Eingabe:
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};
Erwartete Ausgabe:
long long expected = 6;Eingabe:
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};
Erwartete Ausgabe:
long expected = 6;Erläuterung
Die 9 direkt zu überqueren kostet 9 + 1 = 10. Nach unten, entlang der untersten Zeile und wieder nach oben betritt sechs Zellen mit Kosten 1, insgesamt 6.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Verwende eine Prioritätswarteschlange, die nach bisher zurückgelegten Kosten plus Manhattan-Distanz zum Ziel sortiert ist.
Hinweis 2
Verfolge die bisher beste gefundene Kosten für jede Zelle und expandiere eine Zelle nur, wenn dieser Pfad sie verbessert.
Hinweis 3
Behandle Wände sowie blockierte Start- oder Zielzellen als unmöglich, und vergiss nicht, dass das Betreten der Startzelle kostenlos ist.
Erwartete Komplexität
Zeit O(rows * cols log(rows * cols)), zusätzlicher Speicher O(rows * cols)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.