पायथन में लक्ष्य तक पहुँचने के लिए सबसे छोटा रास्ता खोजने का कार्यक्रम

मान लीजिए, हमें एक ग्रिड दिया गया है जहां कोशिकाओं में 'X', 'O', '*' और '#' जैसे विभिन्न प्रतीक होते हैं और प्रतीकों के विभिन्न अर्थ होते हैं।

'#' वह लक्ष्य सेल है जिस तक हम पहुंचना चाहते हैं।
'O' एक निःशुल्क सेल है जिसके द्वारा हम लक्ष्य सेल तक जा सकते हैं।
'*' सेल में हमारी स्थिति है।
'X' एक अवरुद्ध सेल है, जिससे हम यात्रा नहीं कर सकते।

हमें ग्रिड में अपनी वर्तमान स्थिति से लक्ष्य सेल तक पहुंचने के लिए आवश्यक चालों की संख्या का पता लगाना होगा। यदि लक्ष्य प्राप्त नहीं होता है, तो हम -1 लौटते हैं। कार्यक्रम के इनपुट के रूप में ग्रिड दिया गया है।

तो, अगर इनपुट पसंद है

X	X	ओ	X
X	X	*	X
X	#	ओ	X
X	X	X	X

तो आउटपुट 2

. होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

m :=ग्रिड की पंक्ति गणना
n :=ग्रिड की कॉलम संख्या
0 से मी की सीमा में i के लिए, करें
- जे के लिए 0 से n की सीमा में, करें
  - यदि ग्रिड[i, j] "*" के समान है, तो
    - लूप से बाहर आएं
  - अन्यथा,
    - अगले पुनरावृत्ति के लिए जाएं
  - लूप से बाहर आएं
उत्तर:=0
कतार :=पूर्णांक युग्म (i, j) वाली एक नई सूची
ग्रिड[i, j] :="X"
जबकि कतार खाली नहीं है, करें
- उत्तर:=उत्तर + 1
- newq :=एक नई सूची
- प्रत्येक i, j के लिए कतार में, do
  - प्रत्येक ii के लिए, jj in(i-1, j) ,(i, j-1) ,(i, j+1) ,(i+1, j), do
    - यदि 0 <=ii
    - यदि ग्रिड[ii, jj] "#" के समान है, तो
      - वापसी उत्तर
    - newq के अंत में ii, jj डालें
    - ग्रिड[ii, jj] :="X"
कतार :=newq

वापसी -1

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

def solve(grid):
   m, n = len(grid), len(grid[0])
   for i in range(m):
      for j in range(n):
         if grid[i][j] == "*": break
      else: continue
      break
   ans = 0
   queue = [(i, j)]
   grid[i][j] = "X"
   while queue:
      ans += 1
      newq = []
      for i, j in queue:
         for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
            if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
               if grid[ii][jj] == "#": return ans
               newq.append((ii, jj))
               grid[ii][jj] = "X"
      queue = newq
   return -1

print(solve([['X', 'X', 'O', 'X'],['X', 'X', '*', 'X'],['X', '#',
'O', 'X'],['X', 'X', 'X', 'X']]))

इनपुट

[['X', 'X', 'O', 'X'],
['X', 'X', '*', 'X'],
['X', '#', 'O', 'X'],
['X', 'X', 'X', 'X']]