পাইথনে ম্যাট্রিক্সের সব সেল এক রঙে করার ন্যূনতম অপারেশন সংখ্যা খুঁজে বের করার প্রোগ্রাম

মনে করুন একটি ২ডি ম্যাট্রিক্স M আছে। প্রতিটি সেলে রঙের মান আছে। সন্নিহিত সেল (উপর, নিচ, বাম, ডান) একই রঙ থাকলে গ্রুপ বানান। একটি অপারেশনে এক গ্রুপের সব সেল এক রঙে করা যায়। সব সেল এক রঙে করার ন্যূনতম অপারেশন খুঁজে বের করতে হবে। একবার রঙ বদলে দিলে সেটি আবার চেঞ্জ করা যায় না।

ইনপুট ম্যাট্রিক্স টেবিল দেওয়া আছে, আউটপুট ২।

সমাধানের ধাপসমূহ

যদি ম্যাট্রিক্স খালি হয়, ০ ফেরত দিন
dfs(i, j, matrix, val) ফাংশন সংজ্ঞায়িত করুন
- বাউন্ডারি চেক, ভিজিটেড চেক (-1), ভ্যালু মিল চেক
- মিললে -1 চিহ্নিত করুন এবং ৪ দিক ডিএফএস কল করুন
মূল মেথড থেকে:
- n, m := সারি, কলাম
- d := ডিফল্টডিক্ট(int)
- সব সেলে ভিজিট করুন, যদি -1 না হয়, d[val]++, dfs কল করুন
- d-এর ভ্যালু অনুযায়ী সর্ট করুন, safe := সর্বোচ্চ ফ্রিকোয়েন্সি वाला কী
- res := 0, safe ছাড়া সব কী-এর ভ্যালু যোগ করুন
- res ফেরত দিন

উদাহরণ

from collections import defaultdict
class Solution:
    def solve(self, matrix):
        if not matrix:
            return 0
        def dfs(i, j, matrix, val):
            n, m = len(matrix), len(matrix[0])
            if i < 0 or i > n - 1 or j < 0 or j > m - 1:
                return
            if matrix[i][j] == -1:
                return
            if matrix[i][j] == val:
                matrix[i][j] = -1
                dfs(i, j + 1, matrix, val)
                dfs(i + 1, j, matrix, val)
                dfs(i, j - 1, matrix, val)
                dfs(i - 1, j, matrix, val)
            else:
                return
        n, m = len(matrix), len(matrix[0])
        d = defaultdict(int)
        for i in range(n):
            for j in range(m):
                val = matrix[i][j]
                if val != -1:
                    d[val] += 1
                    dfs(i, j, matrix, val)
        l = sorted(d,key=lambda x: d[x])
        safe = l[-1]
        res = 0
        for k, v in d.items():
            if k != safe:
                res += v
        return res

ob = Solution()
matrix = [[2, 2, 2, 2],[1, 1, 1, 1],[2, 3, 2, 1]]
print(ob.solve(matrix))

ইনপুট

matrix = [[2, 2, 2, 2],[1, 1, 1, 1],[2, 3, 2, 1]]