नाइट की चाल
आपको 8×8 का एक ग्रिड दिया गया है, जहाँ पंक्तियाँ ऊपर से नीचे की ओर 0 से 7 तक और स्तंभ बाएँ से दाएँ की ओर 0 से 7 तक क्रमांकित हैं। ग्रिड पर एक नाइट को
(a, b) खाने में रखा गया है। नाइट शतरंज के मानक नियमों के अनुसार चलता है, जिनमें:- नाइट
Lआकार में चलता है। वह क्षैतिज या ऊर्ध्वाधर दिशा में दो कदम जाकर, उसके बाद पहले कदम से लम्बवत (परपेंडिकुलर) एक कदम चलता है।
- नाइट 8×8 ग्रिड की सीमाओं के बाहर नहीं जा सकता।
प्रत्येक नाइट की चाल का एक मूल्य (cost) होता है। यदि नाइट से में जाता है तो इस चाल की लागत (cost)
y⋅r + x⋅c के रूप में परिभाषित है।शुरुआती स्थिति
(a, b) से नाइट को ग्रिड के हर अन्य खाने में पहुँचाने के लिए न्यूनतम आवश्यक लागत निकालना आपका काम है।इस कार्य के लिए, एक प्रोग्राम लिखिए जो नाइट की आरंभिक स्थिति इनपुट में लेता है और फिर हर खाने के लिए न्यूनतम लागत (minimum cost) को आउटपुट करता है।
इनपुट (Input)
इनपुट में एक ही पंक्ति होती है, जिसमें दो रिक्त-चिन्ह (space) से अलग किए गए पूर्णांक
a और b (0 ≤ a, b ≤ 7) दिए जाते हैं, जो नाइट की आरंभिक स्थिति को दर्शाते हैं।आउटपुट (Output)
आठ पंक्तियाँ प्रिंट करें, जिनमें प्रत्येक पंक्ति में आठ पूर्णांक रिक्त-चिन्ह से अलग किए गए हों। ग्रिड में
(i, j) खाने तक (a, b) से नाइट को पहुँचाने की न्यूनतम लागत j-वें कॉलम में और i-वीं पंक्ति में प्रदर्शित होनी चाहिए।उदाहरण (Examples)
Input | Output |
1 1 | 13 11 11 3 17 29 43 53
11 0 13 14 19 18 41 64
11 13 9 5 15 31 45 55
3 14 5 22 23 26 45 72
17 19 15 23 25 43 59 73
29 18 31 26 43 58 69 98
43 41 45 45 59 69 97 123
53 64 55 72 73 98 123 146 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB