একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে (১ = স্থল, ০ = জল)। একটি দ্বীপ হলো ১-দের গ্রুপ যা জল বা এজ দিয়ে ঘেরা। যেসব দ্বীপ পুরোপুরি জল দিয়ে ঘেরা (কোনো এজ স্পর্শ করে না) সেগুলো ০-তে কনভার্ট করতে হবে। আউটপুটে সংশোধিত ম্যাট্রিক্স রিটার্ন করুন।
উদাহরণ: ইনপুট ম্যাট্রিক্স → আউটপুট ম্যাট্রিক্স যেখানে মাঝপথের দ্বীপ গিয়েছে, কোণার দ্বীপগুলো থাকল।
সমাধানের ধাপসমূহ (BFS from Edges)
row, col := সারি ও কলাম। B := শূন্য ম্যাট্রিক্স (আউটপুট)। seen := সেট।
প্রতিটি সেল (i,j) এর জন্য:
যদি সেল এজে (i=0 বা row-1 বা j=0 বা col-1) না থাকে, তবে স্কিপ করুন (কারণ আমরা শুধু এজ-কানেক্টেড দ্বীপ রাখব)।
যদি
(i,j) seen-এ থাকে বাA[i][j]==0, স্কিপ করুন।BFS চালিয়ে এই কম্পোনেন্টের সব সেলকে
B-তে ১ করুন এবংseen-এ যোগ করুন।
Bরিটার্ন করুন (শুধু এজ-কানেক্টেড দ্বীপ থাকবে, বাকি ০)।
পাইথন কোড উদাহরণ
from collections import deque
class Solution:
def solve(self, A):
row = len(A)
col = len(A[0])
B = [[0 for _ in range(col)] for _ in range(row)]
seen = set()
def nei(i, j):
if i + 1 < row and A[i + 1][j]:
yield (i + 1, j)
if j + 1 < col and A[i][j + 1]:
yield (i, j + 1)
if i - 1 >= 0 and A[i - 1][j]:
yield (i - 1, j)
if j - 1 >= 0 and A[i][j - 1]:
yield (i, j - 1)
for i in range(row):
for j in range(col):
if i not in (0, row - 1) and j not in (0, col - 1):
continue
if (i, j) in seen:
continue
if A[i][j] == 0:
continue
d = deque([(i, j)])
while d:
x, y = d.popleft()
B[x][y] = 1
for x2, y2 in nei(x, y):
if (x2, y2) not in seen:
d.append((x2, y2))
seen.add((x2, y2))
return B
ob = Solution()
matrix = [
[1, 0, 0, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1],
]
print(ob.solve(matrix))ইনপুট
[[1,0,0,0],[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,0,0,1]]
আউটপুট
[[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
