समस्या
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).
सीमाएँ
1 ≤ rows, cols ≤ 100
0 ≤ each cost ≤ 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;व्याख्या
The centre is a wall. Going right twice and down twice (or down then right) enters 4 cells of cost 1: total 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;व्याख्या
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.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Use a priority queue ordered by traveled cost plus Manhattan distance to the goal.
संकेत 2
Track the best cost found so far for each cell, and only expand a cell when this path improves it.
संकेत 3
Treat walls and blocked start or goal cells as impossible, and remember entering the start cell is free.
अपेक्षित जटिलता
O(rows * cols log(rows * cols)) time, O(rows * cols) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।