भारित ग्रिड पर A* खोज प्रोग्रामिंग चैलेंज

समस्या

A* गेम और रोबोटिक्स का क्लासिक पाथफ़ाइंडिंग एल्गोरिदम है। यह सेल को f = g + h के क्रम में खोजता है, जहाँ g अब तक चुकाई गई लागत है और h बची हुई लागत का ह्यूरिस्टिक अनुमान है।

ग्रिड में हर सेल की लागत है: किसी सेल में जाने पर उसके मान जितनी लागत लगती है, और 0 एक दीवार है जिसमें नहीं जाया जा सकता। आप start से शुरू करते हैं (इसकी लागत नहीं चुकाई जाती) और ऊपर, नीचे, बाएँ या दाएँ चल सकते हैं।

ह्यूरिस्टिक के रूप में मैनहट्टन दूरी |row - goal_row| + |col - goal_col| के साथ A* का उपयोग करें। हर खुले सेल की लागत कम से कम 1 है, इसलिए यह ह्यूरिस्टिक कभी ज़्यादा अनुमान नहीं लगाता और A* इष्टतम उत्तर देता है।

a_star_cost(grid, start, goal) लागू करें।

इनपुट

grid: सेल लागतों का मैट्रिक्स (0 = दीवार)।

start, goal: [row, col] के रूप में स्थितियाँ।

आउटपुट

goal तक पहुँचने की न्यूनतम कुल लागत लौटाएँ, या -1 अगर वहाँ नहीं पहुँचा जा सकता (जिसमें start या goal के दीवार होने का मामला भी शामिल है)।

सीमाएँ

1 ≤ पंक्तियाँ, कॉलम ≤ 100

0 ≤ हर लागत ≤ 9

उदाहरण

उदाहरण 1

इनपुट:
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;

व्याख्या

बीच का सेल दीवार है। दो बार दाएँ और दो बार नीचे (या पहले नीचे फिर दाएँ) जाने पर लागत 1 वाले 4 सेल में प्रवेश होता है, कुल 4।

उदाहरण 2

इनपुट:
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।

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

भारित ग्रिड पर A* खोज

आप क्या सीखेंगे

समस्या

इनपुट

आउटपुट

सीमाएँ

उदाहरण

व्याख्या

व्याख्या

संदर्भ

समुदाय समाधान