k এর সর্বাধিক মান খুঁজে বের করার প্রোগ্রাম যার জন্য আমরা পাইথনে নিরাপদ দূরত্ব বজায় রাখতে পারি

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে। এখানে 0 একটি খালি ঘরকে বোঝায়, এবং একটি 1 একজন ব্যক্তির সাথে একটি ঘর নির্দেশ করে। দুটি কক্ষের মধ্যে দূরত্ব হল x স্থানাঙ্কের পার্থক্য এবং y স্থানাঙ্কের পার্থক্যের মধ্যে সর্বাধিক মান। এখন ম্যাট্রিক্সকে একটি ফ্যাক্টর k দিয়ে নিরাপদ বলে মনে করা হয় যদি একটি খালি বর্গ থাকে যাতে ম্যাট্রিক্সের প্রতিটি ব্যক্তির সেল থেকে দূরত্ব এবং ম্যাট্রিক্সের প্রতিটি দিক k এর থেকে বেশি বা সমান হয়। আমাদের কে ফ্যাক্টরের সর্বোচ্চ মান খুঁজে বের করতে হবে যার জন্য আমরা নিরাপদ থাকতে পারি।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 1, যেমন মধ্য কক্ষে সেল থেকে গ্রিডের প্রতিটি ব্যক্তির দূরত্ব কমপক্ষে 1।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• N :=A

  এর আকার

• M :=A[0]

  এর আকার

• i 0 থেকে N রেঞ্জের জন্য, করুন

  • 0 থেকে M রেঞ্জে j এর জন্য, করুন

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

• উত্তর :=0

• i 0 থেকে N রেঞ্জের জন্য, করুন

  • 0 থেকে M পরিসরে j-এর জন্য করুন

    • যদি 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

        এর সর্বাধিক

• রিটার্ন (উত্তর + 1) / 2

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

শ্রেণীর সমাধান:def solve(self, A):N =len(A) M =len(A[0]) এর জন্য i রেঞ্জে(N):j এর জন্য রেঞ্জ(M):A[i][ j] ^=1 ans =0 in range(N):রেঞ্জে j এর জন্য(M):যদি i এবং j এবং 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) ফেরত (উত্তর + 1) ) // 2ob =সমাধান()ম্যাট্রিক্স =[ [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))

ইনপুট

আউটপুট

1