Đề bài
A* là thuật toán tìm đường kinh điển trong game và robot. Nó duyệt các ô theo thứ tự f = g + h, trong đó g là chi phí đã trả và h là ước lượng heuristic của chi phí còn lại.
Lưới chứa chi phí của từng ô: đi vào một ô tốn đúng giá trị của ô đó, và 0 là tường không thể đi vào. Bạn bắt đầu ở start (không trả chi phí ô này) và có thể đi lên, xuống, trái hoặc phải.
Dùng A* với heuristic là khoảng cách Manhattan |row - goal_row| + |col - goal_col|. Mọi ô đi được đều tốn ít nhất 1, nên heuristic này không bao giờ ước lượng quá và A* trả về kết quả tối ưu.
Hãy viết a_star_cost(grid, start, goal).
Đầu vào
grid: Ma trận chi phí của các ô (0 = tường).
start, goal: Vị trí dạng [row, col].
Đầu ra
Trả về tổng chi phí nhỏ nhất để đến goal, hoặc -1 nếu không thể đến (kể cả khi start hoặc goal là tường).
Ràng buộc
1 ≤ số hàng, số cột ≤ 100
0 ≤ mỗi chi phí ≤ 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;Giải thích
Ô giữa là tường. Đi sang phải hai lần rồi xuống hai lần (hoặc xuống rồi sang phải) sẽ đi vào 4 ô chi phí 1, tổng là 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;Giải thích
Đi thẳng qua ô 9 tốn 9 + 1 = 10. Đi xuống, dọc theo hàng cuối rồi đi lên sẽ đi vào sáu ô chi phí 1, tổng là 6.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Dùng priority queue được sắp theo chi phí đã đi cộng với Manhattan distance tới đích.
Gợi ý 2
Theo dõi chi phí tốt nhất đã tìm cho mỗi ô, và chỉ mở rộng một ô khi đường đi hiện tại cải thiện nó.
Gợi ý 3
Xem tường và ô start hoặc goal bị chặn là không thể đi được, và nhớ rằng bước vào ô start là miễn phí.
Độ phức tạp mong đợi
thời gian O(rows * cols log(rows * cols)), bộ nhớ phụ O(rows * cols)
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.