k का अधिकतम मान ज्ञात करने का कार्यक्रम जिसके लिए हम पायथन में सुरक्षित दूरी बनाए रख सकते हैं

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है। यहां 0 एक खाली सेल को दर्शाता है, और 1 एक व्यक्ति के साथ एक सेल को दर्शाता है। दो कोशिकाओं के बीच की दूरी x निर्देशांक में अंतर और y निर्देशांक में अंतर के बीच का अधिकतम मान है। अब मैट्रिक्स को एक कारक k के साथ सुरक्षित माना जाता है यदि कोई खाली वर्ग है जैसे कि मैट्रिक्स में प्रत्येक व्यक्ति के लिए सेल से दूरी, और मैट्रिक्स का प्रत्येक पक्ष k के बराबर या अधिक हो। हमें कारक k का अधिकतम मान ज्ञात करना होगा जिसके लिए हम सुरक्षित रह सकते हैं।

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

तो आउटपुट 1 होगा, क्योंकि मध्य सेल में सेल से ग्रिड में प्रत्येक व्यक्ति की दूरी कम से कम 1 है।

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

• N:=A का आकार

• एम:=ए का आकार[0]

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

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

    • ए[i, j] :=A[i, j] XOR 1

• उत्तर :=0

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

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

    • अगर i और j गैर-शून्य हैं और A[i, j] 1 है, तो

      • A[i, j] :=1 + न्यूनतम A[i-1, j], A[i, j-1] और A[i-1, j-1]

      • ans =अधिकतम A[i, j] और ans

• वापसी (Ans + 1) / 2

उदाहरण

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

class Solution:
def solve(self, A):
   N = len(A)
   M = len(A[0])
   for i in range(N):
      for j in range(M):
         A[i][j] ^= 1
   ans = 0
   for i in range(N):
      for j in range(M):
         if i and j and A[i][j]:
            A[i][j] = 1 + min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1])
            ans = max(A[i][j], ans)
   return (ans + 1) // 2
ob = Solution()
matrix = [
   [0, 0, 0, 0, 0],
   [0, 1, 1, 1, 0],
   [0, 1, 0, 1, 0],
   [0, 1, 1, 1, 0],
   [0, 0, 0, 0, 0],
]
print(ob.solve(matrix))

इनपुट

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

आउटपुट

1