समस्या
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
उदाहरण
इनपुट:
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।
इनपुट:
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।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Travelled cost plus goal तक Manhattan distance के आधार पर ordered priority queue use करें.
संकेत 2
हर cell के लिए अब तक मिला best cost track करें, और सिर्फ तब cell expand करें जब यह path उसे improve करे.
संकेत 3
Walls और blocked start या goal cells को impossible मानें, और याद रखें कि start cell में enter करना free है.
अपेक्षित जटिलता
समय O(rows * cols log(rows * cols)), अतिरिक्त स्थान O(rows * cols)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।