मान लीजिए, हमारे पास एक शतरंज की बिसात और एक विशेष नाइट पीस K है, जो बोर्ड के भीतर L आकार में चलता है। यदि टुकड़ा स्थिति (x1, y1) में है और यदि यह (x2, y2) पर जाता है तो आंदोलन को x2 =x1 ± a के रूप में वर्णित किया जा सकता है; y2 =y1 ± b या x2 =x1 ± b; y2 =y1 ± ए; जहाँ a और b पूर्णांक संख्याएँ हैं। हमें उस शतरंज के टुकड़े के लिए स्थिति (0, 0) से शतरंज की बिसात पर स्थिति (n-1, n-1) तक पहुँचने के लिए न्यूनतम चालों का पता लगाना होगा। यदि कोई स्थिति उपलब्ध नहीं है, तो इसे -1 चिह्नित किया जाता है, अन्यथा, चालों की संख्या वापस कर दी जाती है। हम आउटपुट की n - 1 पंक्तियाँ प्रिंट करेंगे, जहाँ प्रत्येक पंक्ति में i में n - 1 पूर्णांक होंगे जो प्रत्येक j के लिए टुकड़े द्वारा की जाने वाली चालों की न्यूनतम संख्या का वर्णन करते हैं।
इसलिए, यदि इनपुट n =6 जैसा है, तो आउटपुट होगा
5 4 3 2 5 4 -1 2 -1 -1 3 2 -1 -1 -1 2 -1 -1 -1 -1 5 -1 -1 -1 1
शूरवीर के लिए संभावित चालें यदि वह 5x5 शतरंज की बिसात में स्थिति (3, 3) में है।
आउटपुट की पहली पंक्ति में स्थिति (1,1) से (1,5) तक पहुंचने के लिए टुकड़े द्वारा आवश्यक चालों की न्यूनतम संख्या होती है। लगातार पंक्तियाँ समान रूप से प्रत्येक संबंधित I और j मानों के लिए चालों की न्यूनतम संख्या का वर्णन करती हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक फ़ंक्शन को परिभाषित करें path_search() । इसमें i, j, n
. लगेगा-
temp_list :=जोड़े के साथ आरंभ किया गया एक नया नक्शा (-1, -1)
-
Queue_positional :=जोड़े द्वारा आरंभ की गई एक नई सूची (0, 0)
-
ver:=[(i, j) ,(-i, j) ,(i, -j) ,(-i, -j) ,(j, i) ,(j, -i) ,(-j, i) ) ,(-j, -i) ]
-
जबकि क्यू का आकार_स्थिति> 0, करें
-
current_element :=पहला तत्व क्यू_पोज़िशनल से हटाएं
-
क्रिया में प्रत्येक तत्व के लिए करें
-
x:=तत्व[0] + current_element[0]
-
y :=element[1] + current_element[1]
-
अगर -1
-
temp_list[x, y] :=current_element
-
कतार_स्थिति के अंत में जोड़ी (x, y) डालें
-
यदि x, n-1 के समान है और y, n-1 के समान है, तो
-
count_var :=1
-
जबकि temp_list[x,y] समान नहीं है(0, 0) , do
-
count_var :=count_var + 1
-
x, y:=temp_list[x,y]
-
-
वापसी count_var
-
-
-
-
-
वापसी -1
-
मुख्य कार्य/विधि से, निम्न कार्य करें -
-
बोर्ड :=-1 के साथ आरंभ किया गया एक नया नक्शा
-
1 से n की सीमा में i के लिए, करें
-
j के लिए 1 से i की श्रेणी में, करें
-
अगर बोर्ड [i, j] -1 के समान है, तो
-
बोर्ड [i, j] :=path_search(i, j, n)
-
बोर्ड [जे, आई]:=बोर्ड [आई, जे]
-
-
अगर (एन -1) मॉड मैं 0 के समान है, तो
-
बोर्ड[i, i] :=(n - 1) / i
-
-
-
-
1 से n की सीमा में i के लिए, करें
-
j के लिए 1 से n-1 की श्रेणी में, करें
-
प्रिंट (बोर्ड[i, j])
-
-
प्रिंट (बोर्ड[i, n - 1])
-
सोर्स कोड (पायथन)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
from collections import defaultdict def path_search(i, j, n): temp_list = defaultdict(lambda: (-1,-1)) queue_positional = [(0, 0)] ver = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)] while len(queue_positional) > 0: current_element = queue_positional.pop(0) for element in ver: x = element[0] + current_element[0] y = element[1] + current_element[1] if -1 < x < n and -1 < y < n and temp_list[x, y] == (-1,-1): temp_list[x, y] = current_element queue_positional.append((x, y)) if x == n - 1 and y == n - 1: count_var = 1 while temp_list[x,y]!=(0,0): count_var += 1 x, y = temp_list[x,y] return count_var return -1 def solve(n): board = defaultdict(lambda: -1) for i in range(1, n): for j in range(1, i): if board[i, j] == -1: board[i, j] = path_search(i, j, n) board[j, i] = board[i, j] if (n - 1) % i == 0: board[i, i] = (n - 1) / i for i in range(1, n): for j in range(1, n - 1): print(int(board[i, j]), end = ' ') print(int(board[i, n - 1])) solve(6)
इनपुट
6
आउटपुट
5 4 3 2 5 4 -1 2 -1 -1 3 2 -1 -1 -1 2 -1 -1 -1 -1 5 -1 -1 -1 1