मैट्रिक्स उत्पन्न करने का कार्यक्रम जहां प्रत्येक कोशिका मैनहट्टन में निकटतम 0 से पायथन दूरी रखती है

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है। हमें एक ही मैट्रिक्स को खोजना होगा, लेकिन प्रत्येक सेल का मान मैनहट्टन दूरी से निकटतम 0 होगा। हम मान सकते हैं कि मैट्रिक्स में कम से कम एक 0 मौजूद है।

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

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

क्योंकि केवल निचले बाएँ सेल में निकटतम 0 से 2 की दूरी है।

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

• m:=मैट्रिक्स की पंक्ति का आकार, n:=मैट्रिक्स का स्तंभ आकार
• y के लिए 0 से m की सीमा में, करें
  • 0 से n की श्रेणी में x के लिए, करें
    • यदि मैट्रिक्स [y, x] शून्य नहीं है, तो
      • मैट्रिक्स[y, x] :=अनंत
• y के लिए 0 से m की सीमा में, करें
  • 0 से n की श्रेणी में x के लिए, करें
    • यदि y शून्य नहीं है, तो
      • मैट्रिक्स[y, x] =न्यूनतम मैट्रिक्स[y, x] और मैट्रिक्स[y-1, x] + 1
    • यदि x शून्य नहीं है, तो
      • मैट्रिक्स[y, x] =न्यूनतम मैट्रिक्स[y, x] और मैट्रिक्स[y, x - 1] + 1
• y के लिए m - 1 से 0 की सीमा में, 1 से घटाएं
  • x के लिए n - 1 से 0 की श्रेणी में, 1 से घटाएं
    • यदि y + 1 <मी, तो
      • मैट्रिक्स[y, x] =न्यूनतम मैट्रिक्स[y, x] और मैट्रिक्स[y + 1, x] + 1
    • यदि x + 1
    • मैट्रिक्स[y, x] =न्यूनतम मैट्रिक्स[y, x] और मैट्रिक्स[y, x + 1] + 1

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

उदाहरण

import math
class Solution:
   def solve(self, matrix):
      m, n = len(matrix), len(matrix[0])
      for y in range(m):
         for x in range(n):
            if matrix[y][x]:
               matrix[y][x] = math.inf
      for y in range(m):
         for x in range(n):
            if y:
               matrix[y][x] = min(matrix[y][x], matrix[y - 1][x] + 1)
            if x:
               matrix[y][x] = min(matrix[y][x], matrix[y][x - 1] + 1)
      for y in range(m - 1, -1, -1):
         for x in range(n - 1, -1, -1):
            if y + 1 < m:
               matrix[y][x] = min(matrix[y][x], matrix[y + 1][x] + 1)
            if x + 1 < n:
               matrix[y][x] = min(matrix[y][x], matrix[y][x + 1] + 1)
      return matrix
ob = Solution()
matrix = [ [1, 0, 1], [1, 0, 1], [1, 1, 0] ]
print(ob.solve(matrix))

इनपुट

[[1, 0, 1],
[1, 0, 1],
[1, 1, 0] ]

आउटपुट

[[1, 0, 1], [1, 0, 1], [2, 1, 0]]