পাইথনে দ্বীপগুলির মধ্যে সবচেয়ে ছোট সেতুর দূরত্ব খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে, যেখানে 0 জলের প্রতিনিধিত্ব করে এবং 1 ভূমিকে প্রতিনিধিত্ব করে। একটি দ্বীপ হল 4টি দিকে 1sকে সংযুক্ত করার একটি গ্রুপ। দ্বীপগুলি হয় 0s (জল) দ্বারা বা প্রান্ত দ্বারা বেষ্টিত। আমাদের সবচেয়ে ছোট সেতুর দৈর্ঘ্য খুঁজে বের করতে হবে যা দুটি দ্বীপকে সংযুক্ত করে।

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

তাহলে আউটপুট হবে 1। এটি (1,0) এর সাথে (1,2) পয়েন্ট সংযোগ করবে।

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

• সারি :=ম্যাট্রিক্সের সারি গণনা

• col :=ম্যাট্রিক্সের কলাম সংখ্যা

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এর জন্য i, j, s

  লাগবে

• যদি (i, j) s হয়, তাহলে

  • ফেরত

• যদি mat[i, j] 0 এর মত হয়, তাহলে

  • ফেরত

• s

  -এ (i, j) সন্নিবেশ করান

• যদি i - 1>=0, তাহলে

  • dfs(i - 1, j, s)

• i + 1 <সারি হলে

  • dfs(i + 1, j, s)

• যদি j - 1>=0 হয়, তাহলে

  • dfs(i, j - 1, s)

• যদি j + 1

  • dfs(i, j + 1, s)

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• দেখা হয়েছে :=একটি নতুন সেট

• আমি 0 থেকে সারি রেঞ্জের জন্য, করুন

  • যদি সাইজ> 0 দেখা যায়, তাহলে

    • লুপ থেকে বেরিয়ে আসুন

  • j-এর জন্য 0 থেকে col, do

    • যদি mat[i, j] 1 এর মত হয়, তাহলে

      • dfs(i, j, দেখা)

      • লুপ থেকে বেরিয়ে আসুন

• q :=একটি ডবল শেষ সারি

• দেখা প্রতিটি জমির জন্য, করুন

  • (i, j) :=জমি

  • যদি i - 1>=0 এবং mat[i - 1, j] 0 এর মত হয়, তাহলে

    • q

      এর শেষে সন্নিবেশ করুন (i - 1, j, 1)

  • যদি i + 1

    • q

      এর শেষে সন্নিবেশ করুন (i + 1, j, 1)

  • যদি j - 1>=0 এবং mat[i, j - 1] 0 এর সমান হয়, তাহলে

    • q

      এর শেষে সন্নিবেশ করুন (i, j - 1, 1)

  • যদি j + 1

    • q

      এর শেষে সন্নিবেশ করুন (i, j + 1, 1)

• যখন q> 0 এর মাপ, do

  • (i, j, dist) :=q এর বাম আইটেম, এবং q এর বাম থেকে আইটেম মুছুন

  • যদি (i, j) দেখা যায়, তাহলে

    • পরবর্তী পুনরাবৃত্তির জন্য যান

  • চিহ্ন (i, j) যেমন দেখা গেছে

  • যদি mat[i, j] 1 এর মত হয়, তাহলে

    • প্রত্যাবর্তন জেলা - 1

  • যদি i - 1>=0, তাহলে

    • q

      এর শেষে সন্নিবেশ করুন (i - 1, j, dist + 1)

  • যদি i + 1 <সারি অ-শূন্য হয়, তাহলে

    • q

      এর শেষে সন্নিবেশ করুন (i + 1, j, dist + 1)

  • যদি j - 1>=0 হয়, তাহলে

    • q

      এর শেষে সন্নিবেশ করুন (i, j - 1, dist + 1)

  • যদি j + 1

    • q

      এর শেষে সন্নিবেশ করুন (i, j + 1, dist + 1)

উদাহরণ

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

import collections
class Solution:
   def solve(self, mat):
      row = len(mat)
      col = len(mat[0])
      def dfs(i, j, s):
         if (i, j) in s:
            return
         if mat[i][j] == 0:
            return
         s.add((i, j))
         if i - 1 >= 0:
            dfs(i - 1, j, s)
         if i + 1 < row:
            dfs(i + 1, j, s)
         if j - 1 >= 0:
            dfs(i, j - 1, s)
         if j + 1 < col:
            dfs(i, j + 1, s)
      seen = set()
      for i in range(row):
         if len(seen) > 0:
            break
         for j in range(col):
            if mat[i][j] == 1:
               dfs(i, j, seen)
               break
      q = collections.deque()
      for land in seen:
         i, j = land
         if i - 1 >= 0 and mat[i - 1][j] == 0:
            q.append((i - 1, j, 1))
         if i + 1 < row and mat[i + 1][j] == 0:
            q.append((i + 1, j, 1))
         if j - 1 >= 0 and mat[i][j - 1] == 0:
            q.append((i, j - 1, 1))
         if j + 1 < col and mat[i][j + 1] == 0:
            q.append((i, j + 1, 1))
      while len(q) > 0:
         i, j, dist = q.popleft()
         if (i, j) in seen:
            continue
         seen.add((i, j))
         if mat[i][j] == 1:
            return dist - 1
         if i - 1 >= 0:
            q.append((i - 1, j, dist + 1))
         if i + 1 < row:
            q.append((i + 1, j, dist + 1))
         if j - 1 >= 0:
            q.append((i, j - 1, dist + 1))
         if j + 1 < col:
            q.append((i, j + 1, dist + 1))
ob = Solution()
matrix = [
   [0, 0, 1],
   [1, 0, 1],
   [1, 0, 0],
]
print(ob.solve(matrix))

ইনপুট

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

আউটপুট

1