पायथन में सभी कोशिकाओं को एक ही रंग में आवश्यक संचालन की संख्या की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास दो-आयामी मैट्रिक्स एम है। अब प्रत्येक सेल में एक मान होता है जो उसके रंग का प्रतिनिधित्व करता है, और एक ही रंग के साथ आसन्न कोशिकाओं (ऊपर, नीचे, बाएं, दाएं) को एक साथ समूहीकृत किया जाना है। अब, एक ऑपरेशन पर विचार करें जहां हम सभी कोशिकाओं को एक समूह में किसी रंग में सेट करते हैं। फिर अंत में आवश्यक संक्रियाओं की न्यूनतम संख्या ज्ञात कीजिए ताकि प्रत्येक सेल का रंग समान हो। और जब रंग बदल जाता है, तो उसे फिर से सेट नहीं किया जा सकता है।

तो, अगर इनपुट पसंद है

तब आउटपुट 2 होगा, क्योंकि हम समूह को 2 से रंग के रूप में 1 में भर सकते हैं और फिर 3 को 1 से भर सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे-

• अगर मैट्रिक्स खाली है, तो

  • वापसी 0

• फ़ंक्शन को परिभाषित करें dfs() । यह i, j, मैट्रिक्स, वैल लेगा

• n :=मैट्रिक्स की पंक्ति गणना, m :=मैट्रिक्स की कॉल संख्या

• अगर मैं <0 या i> n - 1 या j <0 या j> m -1, तो

  • वापसी

• यदि मैट्रिक्स [i, j] -1 के समान है, तो

  • वापसी

• यदि मैट्रिक्स [i, j] वैल के समान है, तो

  • मैट्रिक्स [i, j] :=-1

  • dfs(i, j + 1, मैट्रिक्स, वैल)

  • dfs(i + 1, j, मैट्रिक्स, वैल)

  • dfs(i, j-1, मैट्रिक्स, वैल)

  • dfs(i-1, j, मैट्रिक्स, वैल)

• अन्यथा,

  • वापसी

• मुख्य विधि से, निम्न कार्य करें-

• n :=मैट्रिक्स की पंक्ति गणना, m :=मैट्रिक्स की कॉल संख्या

• d :=खाली नक्शा

• मेरे लिए 0 से n-1 की सीमा में, करें

  • j के लिए 0 से m-1 की सीमा में, करें

  • वैल:=मैट्रिक्स[i, j]

  • अगर वैल -1 के समान नहीं है, तो

  • डी [वैल]:=डी [वैल] + 1

  • dfs(i, j, मैट्रिक्स, वैल)

• f के शब्दकोश तत्वों को उनके मूल्यों के आधार पर क्रमबद्ध करें

• सुरक्षित:=एल का अंतिम तत्व

• रेस :=0

• प्रत्येक कुंजी मान जोड़े k और d के v के लिए, करें

  • यदि k सुरक्षित के समान नहीं है, तो

  • रेस :=रेस + वी

• रिटर्न रेस

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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