पायथन में निचले दाएं कोने तक पहुंचने के लिए आवश्यक न्यूनतम संख्या में कोशिकाओं को खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक 2D ग्रिड है जो एक भूलभुलैया का प्रतिनिधित्व करता है जहां 0 खाली जगह के लिए है, और 1 दीवार है। हम ग्रिड से शुरू करेंगे [0, 0], हमें ग्रिड के निचले दाएं कोने तक पहुंचने के लिए न्यूनतम वर्गों की संख्या ज्ञात करनी होगी। यदि हम नहीं पहुँच सकते हैं, तो -1 पर लौटें।

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

0	0	0
1	0	0
1	0	0

तो आउटपुट 5

. होगा

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

आर:=ग्रिड की पंक्ति गणना, सी:=ग्रिड की कॉलम गणना
q :=[0, 0, 1] जब A[0, 0] 1 है अन्यथा एक नई सूची
ए[0, 0] :=1
क्यू में प्रत्येक (आर, सी, डी) के लिए, करो
- अगर (आर, सी) (आर -1, सी -1) के समान है, तो
  - वापसी d
- - [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1)] में प्रत्येक (x, y) के लिए, करें
    - यदि x 0 से R की श्रेणी में है और y 0 से C की श्रेणी में है और A[x, y] 0 के समान है, तो
      - ए[एक्स, वाई] :=1
      - q के अंत में (x, y, d + 1) डालें
वापसी -1

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

उदाहरण

class Solution:
   def solve(self, A):
      R, C = len(A), len(A[0])
      q = [(0, 0, 1)] if not A[0][0] else []
      A[0][0] = 1
      for r, c, d in q:
         if (r, c) == (R − 1, C − 1):
            return d
         for x, y in [(r + 1, c), (r − 1, c), (r, c + 1), (r, c −1)]:
            if 0 <= x < R and 0 <= y < C and A[x][y] == 0:
               A[x][y] = 1
               q.append((x, y, d + 1))
      return −1
ob = Solution()
grid = [
   [0, 0, 0],
   [1, 0, 0],
   [1, 0, 0]
]
print(ob.solve(grid))

इनपुट

grid = [ [0, 0, 0], [1, 0, 0], [1, 0, 0] ]