यह जांचने के लिए कार्यक्रम कि क्या पायथन में भूलभुलैया से बाहर निकलने के लिए कम्पास के उपयोग की संख्या पर्याप्त है

मान लीजिए, हम कोई खेल खेल रहे हैं जहाँ हम एक चक्रव्यूह में फंस गए हैं। हमें भूलभुलैया से बाहर निकलने का रास्ता खोजना होगा। भूलभुलैया को x m मैट्रिक्स के रूप में प्रस्तुत किया जा सकता है, जहाँ n पंक्तियों की संख्या है और m स्तंभों की संख्या है। मैट्रिक्स के प्रत्येक सेल/तत्व में 'ओ', 'डी', 'एस', या '-' कोई भी प्रतीक होता है। 'ओ' का मतलब है कि रास्ता अवरुद्ध है, 'डी' भूलभुलैया से बाहर निकलने का रास्ता है, 'एस' हमारी शुरुआती स्थिति है, और '-' का मतलब है कि हम रास्ते से आगे बढ़ सकते हैं। हम किसी भी '-' चिह्नित सेल में से स्वतंत्र रूप से घूम सकते हैं। अब, हमारे पास एक कंपास भी है जिसके उपयोग से हम भूलभुलैया से बाहर निकलने का रास्ता ('डी' सेल) ढूंढ सकते हैं। जब हमें दिशा ढूंढनी होती है तो हमें कंपास का उपयोग करना होता है। लेकिन, हम कंपास का अधिकतम k बार उपयोग कर सकते हैं। एक मैट्रिक्स के रूप में भूलभुलैया को देखते हुए और कितनी बार हम कंपास का उपयोग कर सकते हैं; हमें यह पता लगाना होगा कि क्या हम केवल कई बार कंपास का उपयोग करके भूलभुलैया से बाहर निकल सकते हैं। यदि संभव हो तो हम ट्रू लौटाते हैं, अन्यथा हम असत्य लौटाते हैं।

तो, अगर इनपुट ग्रिड की तरह है =

-	O	-	O	-	-	-	-	-	-	O
-	O	D	-	O	-	O	O	O	-	O
-	O	O	-	O	-	O	O	O	-	O
-	O	O	-	O	-	O	S	-	-	-
-	-	-	-	-	-	O	O	O	O	-

एन =4, एम =11, के =3; तो आउटपुट ट्रू होगा।

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

एक फ़ंक्शन को परिभाषित करें path_search() । इसमें curr_pos, ग्रिड, Total_rows, Total_cols, k, पूर्ववर्ती
. लगेगा
- x:=curr_pos का x मान
- y:=y curr_pos का मान
- अगर ग्रिड [x, y] "*" के समान है, तो
  - यदि k, 0 के समान है, तो
    - सही लौटें
  - अन्यथा,
    - झूठी वापसी
  - अन्यथा,
    - जनक :=पूर्ववर्ती[curr_pos]
    - succ_pos :=succesor_positions(curr_pos, grid, total_rows, total_cols, parent) के वापसी मूल्यों से एक नई सूची
    - use_compass :=सच है अगर succ_pos का आकार> 1
    - succ_pos में प्रत्येक स्थिति के लिए, करें
      - पूर्ववर्ती [स्थिति] :=curr_pos
      - अगर use_compass गैर-शून्य है, तो
        
        path_search(स्थिति, ग्रिड, Total_rows, Total_cols, k-1, पूर्ववर्ती)
      - अन्यथा,
        
        path_search(स्थिति, ग्रिड, Total_rows, Total_cols, k, पूर्ववर्ती)
फ़ंक्शन succesor_positions() परिभाषित करें। इसमें curr_pos, ग्रिड, Total_rows, Total_cols, पैरेंट
. लगेगा
- x:=curr_pos का x मान
- y:=y curr_pos का मान
- succ_pos :=एक नई सूची
- ओ अगर y> 0, तो
  - बायां :=x, y - 1
  - succ_pos के अंत में बाईं ओर डालें
- अगर y
  - दाएं:=एक्स, वाई + 1
  - succ_pos के अंत में दाएँ डालें
- अगर x> 0, तो
  - ऊपर :=x - 1, y
  - succ_pos के अंत में डालें
- अगर x
  - नीचे :=x + 1, y
  - succ_pos के अंत में नीचे डालें
- अगर succ_pos में प्रत्येक स्थिति के लिए, grid[position[0], pos[1]] है
- "X" के समान नहीं है और pos माता-पिता के समान नहीं है, तो -
  - शर्तों को पूरा करने वाले succ_pos में तत्वों को वापस करें

अब निम्न कार्य करें -

curr_pos :=एक नया खाली जोड़ा
प्रत्येक अनुक्रमणिका i के लिए, ग्रिड में आइटम पंक्ति, करें
- प्रत्येक अनुक्रमणिका j के लिए, पंक्ति में आइटम तत्व, करें
  - यदि तत्व 'M' के समान है, तो
    - curr_pos :=एक नई जोड़ी जिसमें i, j है
पूर्ववर्ती :=एक नया नक्शा जहां curr_pos :=प्रारंभ में शून्य
path_search(curr_pos, ग्रिड, n, m, k, पूर्ववर्ती)

सोर्स कोड (पायथन)

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

def path_search(curr_pos, grid, total_rows, total_cols, k, predecessor):
   x, y = curr_pos
   if grid[x][y] == "D":
      if k == 0:
         print('True')
      else:
         print('False')
   else:
      parent = predecessor[curr_pos]
      succ_pos = list(succesor_positions(curr_pos, grid, total_rows, total_cols, parent))
      use_compass = len(succ_pos) > 1
      for position in succ_pos:
         predecessor[position] = curr_pos
         if use_compass:
            path_search(position, grid, total_rows, total_cols, k - 1, predecessor)
         else:
            path_search(position, grid, total_rows, total_cols, k, predecessor)

def succesor_positions(curr_pos, grid, total_rows, total_cols, pred):
   x, y = curr_pos
   succ_pos = []
   if y > 0:
      left = (x, y - 1)
      succ_pos.append(left)
   if y < total_cols - 1:
      right = (x, y + 1)
      succ_pos.append(right)
   if x > 0:
      up = (x - 1, y)
      succ_pos.append(up)
   if x < total_rows - 1:
      down = (x + 1, y)
      succ_pos.append(down)
   return filter(lambda pos: grid[pos[0]][pos[1]] != "O" and pos != pred, succ_pos)

def solve(grid, n, m, k):
   curr_pos = ()
   for i, row in enumerate(grid):
      for j, element in enumerate(row):
         if element == 'S':
            curr_pos = (i, j)
   path_search(curr_pos, grid, n, m, k, predecessor = {curr_pos: None})

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']]

solve(grid, 4, 11, 3)

इनपुट

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']] , 4, 11, 3

आउटपुट

True