A* — классический алгоритм поиска пути в играх и робототехнике. Он перебирает клетки в порядке f = g + h, где g — уже уплаченная стоимость, а h — эвристическая оценка оставшейся стоимости.
В сетке записана стоимость каждой клетки: вход в клетку стоит её значение, а 0 — стена, в которую нельзя войти. Вы начинаете в start (её стоимость не платится) и можете двигаться вверх, вниз, влево или вправо.
Используйте A* с манхэттенским расстоянием |row - goal_row| + |col - goal_col| в качестве эвристики. Каждая открытая клетка стоит не меньше 1, поэтому эвристика никогда не завышает оценку и A* возвращает оптимальный ответ.
Реализуйте a_star_cost(grid, start, goal).
Входные данные
grid: Матрица стоимостей клеток (0 = стена).
start, goal: Позиции в виде [row, col].
Выходные данные
Верните минимальную суммарную стоимость пути до goal или -1, если до неё нельзя добраться (в том числе когда start или goal — стена).
Ограничения
1 ≤ строки, столбцы ≤ 100
0 ≤ каждая стоимость ≤ 9
Примеры
Ввод:
goal = [2, 2]
grid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
start = [0, 0]
Ожидаемый вывод:
expected = 4Ввод:
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};
Ожидаемый вывод:
long long expected = 4;Ввод:
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};
Ожидаемый вывод:
long expected = 4;Пояснение
Центр — стена. Два шага вправо и два вниз (или вниз, затем вправо) заходят в 4 клетки стоимостью 1, итого 4.
Ввод:
goal = [0, 2]
grid = [
[1, 9, 1],
[1, 9, 1],
[1, 1, 1]
]
start = [0, 0]
Ожидаемый вывод:
expected = 6Ввод:
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};
Ожидаемый вывод:
long long expected = 6;Ввод:
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};
Ожидаемый вывод:
long expected = 6;Пояснение
Пройти прямо через 9 стоит 9 + 1 = 10. Спуститься, пройти по нижней строке и подняться обратно — это шесть клеток стоимостью 1, итого 6.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Используйте priority queue, упорядоченную по уже пройденной стоимости плюс Manhattan distance до цели.
Подсказка 2
Отслеживайте лучшую стоимость, найденную для каждой клетки, и раскрывайте клетку только если этот путь её улучшает.
Подсказка 3
Считайте стены и заблокированные стартовую или целевую клетки невозможными, и помните, что вход в стартовую клетку бесплатен.
Ожидаемая сложность
O(rows * cols log(rows * cols)) по времени, O(rows * cols) по дополнительной памяти
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.