न्यूनतम पथ योग
एक ऐसे ग्रिड पर विचार कीजिए जिसकी ऊँचाई
h और चौड़ाई w है, और जिसमें प्रत्येक सेल में एक पूर्णांक भरा हुआ है। आपका कार्य है कि ऊपर-बाएँ कोने से नीचे-दाएँ कोने तक जाने वाला ऐसा रास्ता ढूँढें, जिससे रास्ते पर आने वाले मानों का योग कम से कम हो। आपको केवल दाएँ या नीचे की ओर बढ़ने की अनुमति है।3 | 2 | 1 | 3 |
1 | 9 | 2 | 3 |
9 | 1 | 5 | 4 |
इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
h और w दिए जाते हैं (1 ≤ h, w ≤ 1000)।इसके बाद की
h पंक्तियों में w पूर्णांक होते हैं, जो स्पेस से अलग किए होते हैं। इन्हें के रूप में प्रस्तुत किया जाता है (1 ≤ g_{i, j} ≤ 1000)।आउटपुट
कार्यक्रम को उस न्यूनतम संभव योग को प्रिंट करना चाहिए, जो ऊपर-बाएँ कोने से नीचे-दाएँ कोने तक पहुँचने पर प्राप्त होता है।
उदाहरण
Input | Output |
3 4
3 2 1 3
1 9 2 3
9 1 5 4 | 15 |
व्याख्या
हम इस तरह चल सकते हैं: 3 → 2 → 1 → 2 → 3 → 4
संकेत 1
डायनामिक प्रोग्रामिंग में प्रयुक्त अवस्था (state) को दो-आयामी एरे के रूप में परिभाषित किया जा सकता है।
संकेत 2
यह अवस्था उस निर्देशांक तक पहुँचने का सर्वश्रेष्ठ संभव समाधान दिखा सकती है (विशेष रूप से,
d[r][c] से आशय पंक्ति r और स्तंभ c तक पहुँचने के लिए सर्वोत्तम रास्ते से है)।यहाँ पर लोभी (greedy) दृष्टिकोण क्यों काम नहीं करता? सोचिए, अगर आप हमेशा सबसे छोटे मान की ओर ही बढ़ें, तो उसकी वजह से कहाँ समस्या आ सकती है?
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB