बैंकिन पायथन में एक गार्ड से सबसे कम दूरी का पता लगाएं

मान लीजिए कि हमारे पास एक मैट्रिक्स है जो तीन अक्षरों 'O', 'G', और 'W' से भरा है जहां 'O' खुले स्थान का प्रतिनिधित्व करता है, 'G' गार्ड का प्रतिनिधित्व करता है और 'डब्ल्यू' एक बैंक में दीवारों का प्रतिनिधित्व कर रहा है, हमें मैट्रिक्स में सभी ओ को एक गार्ड से उनकी सबसे छोटी दूरी के संबंध में बदलना होगा, हम किसी भी दीवार से नहीं जा सकते हैं। आउटपुट में मैट्रिक्स गार्ड को 0 से बदल दिया जाता है और दीवारों को -1 से बदल दिया जाता है।

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

तब आउटपुट होगा

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

• एम:=5

• एन:=5

• dir_row :=[-1, 0, 1, 0]

• dir_col :=[0, 1, 0, -1]

• एक फ़ंक्शन परिभाषित करें is_ok() । यह मैं, जम्मू ले जाएगा

• अगर (i रेंज 0 और M में) या (j रेंज 0 और j N में), तो

  • झूठी वापसी

• सही लौटें

• फ़ंक्शन को परिभाषित करें isSafe() । यह i, j, मैट्रिक्स, परिणाम लेगा

• यदि मैट्रिक्स [i, j] 'O' नहीं है या परिणाम [i, j] -1 नहीं है, तो

  • झूठी वापसी

• सही लौटें

• एक फ़ंक्शन को परिभाषित करें कैलकुलेट_डिस्ट ()। यह मैट्रिक्स लेगा

• परिणाम:=क्रम M x N का एक मैट्रिक्स बनाएं और -1 से भरें

• डबल एंडेड क्यू परिभाषित करें q

• मैं के लिए 0 से एम की सीमा में, करो

  • j के लिए 0 से N की सीमा में, करें

    • परिणाम [i, j] :=-1

    • यदि मैट्रिक्स [i, j] 'G' के समान है, तो

      • स्थिति :=[i, j, 0]

      • q के बाईं ओर स्थित पोज़ डालें

      • परिणाम [i, j] :=0

• जबकि q> 0 का आकार गैर-शून्य है, करें

  • curr :=q से अंतिम तत्व हटाएं

  • एक्स, वाई, जिला:=वर्तमान [0], धारा [1], धारा [2]

  • मेरे लिए 0 से 3 की सीमा में, करें

    • अगर is_ok(x + dir_row[i], y + dir_col[i]) गैर-शून्य है और isSafe(x + dir_row[i], y + dir_col[i], मैट्रिक्स, परिणाम) शून्य नहीं है, तो

      • परिणाम [x + dir_row[i], y + dir_col[i]]:=जिला + 1

      • स्थिति :=[x + dir_row[i], y + dir_col[i], जिला + 1]

      • q के बाईं ओर स्थित पोज़ डालें

• मैं के लिए 0 से एम की सीमा में, करो

  • j के लिए 0 से N की सीमा में, करें

    • परिणाम प्रदर्शित करें[i, j]

  • अगली पंक्ति पर जाएँ

उदाहरण

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

from collections import deque as queue
M = 5
N = 5
dir_row = [-1, 0, 1, 0]
dir_col = [0, 1, 0, -1]
def is_ok(i, j):
   if ((i < 0 or i > M - 1) or (j < 0 or j > N - 1)):
      return False
   return True
def isSafe(i, j,matrix, result):
   if (matrix[i][j] != 'O' or result[i][j] != -1):
      return False
   return True
def calculate_dist(matrix):
   result = [[ -1 for i in range(N)]for i in range(M)]
   q = queue()
   for i in range(M):
      for j in range(N):
         result[i][j] = -1
         if (matrix[i][j] == 'G'):
            pos = [i, j, 0]
            q.appendleft(pos)
            result[i][j] = 0
   while (len(q) > 0):
      curr = q.pop()
      x, y, dist = curr[0], curr[1], curr[2]
   for i in range(4):
      if is_ok(x + dir_row[i], y + dir_col[i]) and isSafe(x + dir_row[i], y + dir_col[i], matrix, result) : result[x + dir_row[i]][y + dir_col[i]] = dist + 1
      pos = [x + dir_row[i], y + dir_col[i], dist + 1]
      q.appendleft(pos)
   for i in range(M):
      for j in range(N):
         if result[i][j] > 0:
            print(result[i][j], end=" ")
         else:
            print(result[i][j],end=" ")
      print()

matrix = [['O', 'O', 'O', 'O', 'G'],
   ['O', 'O', 'O', 'W', 'O'],
   ['O', 'W', 'O', 'O', 'O'],
   ['G', 'W', 'W', 'W', 'O'],
   ['O', 'O', 'O', 'O', 'G']]

calculate_dist(matrix)

इनपुट

[['O', 'O', 'O', 'O', 'G'],
['O', 'O', 'O', 'W', 'O'],
['O', 'W', 'O', 'O', 'O'],
['G', 'W', 'W', 'W', 'O'],
['O', 'O', 'O', 'O', 'G']]

आउटपुट

3 3 2 1 0
2 3 3 -1 1
1 -1 4 3 2
0 -1 -1 -1 1
1 2 2 1 0