পাইথনে দ্বীপগুলোর মাঝপথে শর্টেস্ট ব্রিজের দূরত্ব বের করার প্রোগ্রাম

একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে, যেখানে 0 জল এবং 1 স্থল নির্দেশ করে। একটি দ্বীপ হলো ৪ দিকের সংযুক্ত 1-গুলোর গোষ্ঠী। দ্বীপগুলো হয় জল (0) বা প্রান্তবর্তি প্রান্ত দ্বারা ঘেরা। দুটি দ্বীপ সংযুক্ত করার জন্য শর্টেস্ট ব্রিজের দৈর্ঘ্য বের করতে হবে।

ইনপুট হলে নিচের ম্যাট্রিক্সটি:

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

সমাধানের পদ্ধতি

1. row := ম্যাট্রিক্সের সারি সংখ্যা, col := কলাম সংখ্যা
2. dfs(i, j, s) ফাংশন ডিফাইন করুন:
   • যদি (i, j) ∈ s হয়, তবে রিটার্ন
   • যদি mat[i][j] == 0 হয়, তবে রিটার্ন
   • (i, j) কে s-তে যোগ করুন
   • ৪ দিকের প্রতিটি সেখানে রিকারসিভলি dfs কল করুন
3. মূল মেথড থেকে প্রথম দ্বীপটি খুঁজে বের করে seen সেটে সংরক্ষণ করুন
4. একটি ডেক (deque) q তৈরি করুন এবং প্রথম দ্বীপের সব সেলের প্রতিটি সন্নিহিত জল সেলকে দূরত্ব ১ দিয়ে q-তে ঢুকান
5. বিএফএস চালান:
   • q-তে থেকে সেল বের করুন
   • যদি সেলটি seen-এ থাকে, তবে স্কিপ করুন
   • সেলটি seen-এ মার্ক করুন
   • যদি সেলটি 1 হয় (দ্বিতীয় দ্বীপ), তবে dist - 1 রিটার্ন করুন
   • অন্যথায়, ৪ দিকের সন্নিহিত সেলগুলাকে dist + 1 দিয়ে q-তে ঢুকান

উদাহরণ

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