একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে (০ = খালি, ১ = ব্যক্তি)। দুটি সেলের দূরত্ব = max(|x1-x2|, |y1-y2|) (চেবিশেভ দূরত্ব)। ম্যাট্রিক্স k-সেফ হবে যদি এমন একটি খালি সেল থাকে যেটার দূরত্ব সব ব্যক্তি থেকে এবং গ্রিডের সব প্রান্ত থেকে কমপক্ষে k। সর্বোচ্চ k বের করতে হবে।
উদাহরণ: ৫x৫ ম্যাট্রিক্স যেখানে মাঝপথে ব্যক্তি আছে → আউটপুট 1।
সমাধানের ধাপসমূহ (DP - Largest Square of 1s ইনভার্টেড ম্যাট্রিক্সে)
ম্যাট্রিক্স ইনভার্ট করুন (০↔১)। এখন ১ = খালি সেল।
DP দিয়ে প্রতিটি সেলে সবচেয়ে বড় বর্গের সাইজ বের করুন যেখানে সব সেল ১ (খালি)।
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])যদিA[i][j]==1।সর্বোচ্চ
dpভ্যালু =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
