পাইথনে একই রঙে সমস্ত কক্ষের জন্য প্রয়োজনীয় অপারেশনের সংখ্যা গণনা করার প্রোগ্রাম

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

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

তাহলে আউটপুট হবে 2, যেহেতু আমরা 2টি রঙের সাথে 1-এ পূর্ণ করতে পারি এবং তারপর 3টি 1 দিয়ে পূরণ করতে পারি।

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

• যদি ম্যাট্রিক্স খালি হয়, তাহলে

  • ফেরত 0

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

  লাগবে

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

• যদি i <0 বা i> n - 1 বা j <0 বা j> m - 1, তাহলে

  • ফেরত

• যদি ম্যাট্রিক্স[i, j] -1 এর মত হয়, তাহলে

  • ফেরত

• যদি ম্যাট্রিক্স[i, j] ভ্যালের সমান হয়, তাহলে

  • ম্যাট্রিক্স[i, j] :=-1

  • dfs(i, j + 1, matrix, val)

  • dfs(i + 1, j, ম্যাট্রিক্স, ভ্যাল)

  • dfs(i, j - 1, matrix, val)

  • dfs(i - 1, j, ম্যাট্রিক্স, ভ্যাল)

• অন্যথায়,

  • ফেরত

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

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

• d :=খালি মানচিত্র

• 0 থেকে n-1 রেঞ্জের জন্য, করুন

  • 0 থেকে m-1 রেঞ্জে j-এর জন্য, করুন

  • val :=ম্যাট্রিক্স[i, j]

  • যদি ভ্যাল -1 এর মত না হয়, তাহলে

  • d[val] :=d[val] + 1

  • dfs(i, j, matrix, val)

• f-এর অভিধানের উপাদানগুলিকে তাদের মানগুলির উপর ভিত্তি করে সাজান

• নিরাপদ :=l

  এর শেষ উপাদান

• res :=0

• প্রতিটি কী মানের জন্য d এর k এবং v জোড়া, করুন

  • যদি k নিরাপদ না হয়, তাহলে

  • res :=res + v

• রিটার্ন রিটার্ন

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

উদাহরণ

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]]

আউটপুট

2