मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। यहां 0 एक खाली सेल दर्शाता है, और 1 एक व्यक्ति वाले सेल को दर्शाता है। दो सेल्स के बीच की दूरी x निर्देशांकों के अंतर और y निर्देशांकों के अंतर के बीच का अधिकतम मान है। अब मैट्रिक्स को फैक्टर k के साथ सुरक्षित माना जाता है यदि एक खाली वर्ग ऐसा है कि उस सेल से मैट्रिक्स में प्रत्येक व्यक्ति की दूरी, और मैट्रिक्स की प्रत्येक भुजा की दूरी सभी k से अधिक या बराबर हैं। हमें उस फैक्टर k का अधिकतम मान ज्ञात करना है जिसके लिए हम सुरक्षित रह सकते हैं।
इसलिए, यदि इनपुट इस प्रकार है:
| 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 होगा, क्योंकि मध्य सेल में उस सेल से ग्रिड में प्रत्येक व्यक्ति की दूरी कम से कम 1 है।
हल करने के चरण
N := A का आकार
M := A[0] का आकार
i के लिए 0 से N तक की रेंज में, करें
j के लिए 0 से M तक की रेंज में, करें A[i, j] := A[i, j] XOR 1
ans := 0
i के लिए 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
