দ্বীপের সংখ্যা খুঁজে বের করার প্রোগ্রাম, যেখান থেকে আমরা পাইথনে যেতে পারি না

ধরুন আমাদের একটি বাইনারি ম্যাট্রিক্স আছে। এখানে 1 ভূমি প্রতিনিধিত্ব করে এবং 0 জল প্রতিনিধিত্ব করে। যেকোনো ভূমি থেকে আমরা উপরে, নিচে, বাম বা ডানে যেতে পারি কিন্তু তির্যকভাবে অন্য কোনো ভূমি কোষে যেতে পারি না বা ম্যাট্রিক্সের বাইরে যেতে পারি। আমাদের ভূমি কোষের সংখ্যা খুঁজে বের করতে হবে যেখান থেকে আমরা ম্যাট্রিক্সের বাইরে যেতে পারি না।

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

তাহলে আউটপুট হবে 4, কারণ মাঝখানে 4টি ল্যান্ড স্কোয়ার আছে যেখান থেকে আমরা ম্যাট্রিক্স ছেড়ে যেতে পারি না।

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

• q :=প্রতিটি সারি i এবং কলামের জন্য জোড়ার একটি তালিকা (i, j) যখন ম্যাট্রিক্স[i, j] ভূমি i এবং j সীমানা সূচক হয়
• idx :=0
• প্রতি জোড়ার জন্য (x, y) q, do
  • ম্যাট্রিক্স[x, y] :=0
• যখন idx
• x, y :=q[idx]
• [(-1, 0) ,(0, -1) ,(0, 1) ,(1, 0) ] এ প্রতিটি (dx, dy) এর জন্য, করুন
  • nx :=x + dx
  • ny :=y + dy
  • যদি 0 <=nx <ম্যাট্রিক্সের সারি গণনা এবং 0 <=ny <ম্যাট্রিক্সের কলাম গণনা[nx] এবং ম্যাট্রিক্স[nx, ny] 1 হয়, তাহলে
    • ম্যাট্রিক্স[nx, ny] :=0
    • q এর শেষে সন্নিবেশ (nx, ny) করুন
• idx :=idx + 1

উদাহরণ

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

def solve(matrix):
   q = [(i, j) for i in range(len(matrix)) for j in range(len(matrix[i])) if matrix[i][j] and (i == 0 or i == len(matrix) - 1 or j == 0 or j == len(matrix[i]) - 1)]
   idx = 0
   for x, y in q:
      matrix[x][y] = 0
   while idx < len(q):
      x, y = q[idx]
      for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
         nx, ny = x + dx, y + dy
         if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]:
            matrix[nx][ny] = 0
            q.append((nx, ny))
      idx += 1
   return sum(sum(row) for row in matrix)

matrix = [
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]
print(solve(matrix))

ইনপুট

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

আউটপুট

4