การค้นหา A* บนตารางที่มีน้ำหนัก

A* คืออัลกอริทึมหาเส้นทางแบบคลาสสิกในเกมและหุ่นยนต์ มันสำรวจช่องตามลำดับของ f = g + h โดย g คือค่าใช้จ่ายที่จ่ายไปแล้ว และ h คือค่าประมาณแบบฮิวริสติกของค่าใช้จ่ายที่เหลือ

ตารางเก็บค่าใช้จ่ายของแต่ละช่อง: การเข้าไปในช่องหนึ่งเสียค่าเท่ากับค่าของช่องนั้น และ 0 คือกำแพงที่เข้าไปไม่ได้ คุณเริ่มที่ start (ไม่ต้องจ่ายค่าของช่องนี้) และเดินขึ้น ลง ซ้าย หรือขวาได้

ใช้ A* โดยมีระยะทางแมนฮัตตัน |row - goal_row| + |col - goal_col| เป็นฮิวริสติก ทุกช่องที่เดินได้มีค่าอย่างน้อย 1 ฮิวริสติกนี้จึงไม่เคยประมาณเกิน และ A* จะคืนคำตอบที่เหมาะสมที่สุด

จง implement 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;

อินพุต:
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;

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

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