A* Search on a Weighted Grid

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).

Ràng buộc

1 ≤ rows, cols ≤ 100

0 ≤ each cost ≤ 9

Ví dụ

Đầu vào:
goal = [2, 2]
grid = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
start = [0, 0]

Kết quả mong đợi:
expected = 4

Đầu vào:
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};

Kết quả mong đợi:
long long expected = 4;

Đầu vào:
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};

Kết quả mong đợi:
long expected = 4;

Đầu vào:
goal = [0, 2]
grid = [
    [1, 9, 1],
    [1, 9, 1],
    [1, 1, 1]
]
start = [0, 0]

Kết quả mong đợi:
expected = 6

Đầu vào:
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};

Kết quả mong đợi:
long long expected = 6;

Đầu vào:
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};

Kết quả mong đợi:
long expected = 6;

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

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