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

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

उदाहरण के लिए, यदि इनपुट है:

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

• यदि मैट्रिक्स खाली है, तो 0 वापस करें
• dfs() फंक्शन परिभाषित करें जो i, j, matrix, val लेता है:
  • n := मैट्रिक्स की पंक्ति संख्या, m := मैट्रिक्स की स्तंभ संख्या
  • यदि i < 0 या i > n-1 या j < 0 या j > m-1, तो वापस करें
  • यदि matrix[i][j] == -1, तो वापस करें
  • यदि 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)
  • अन्यथा, वापस करें
• मुख्य विधि से:
  • n := मैट्रिक्स की पंक्ति संख्या, m := मैट्रिक्स की स्तंभ संख्या
  • d := खाली मैप
  • i को 0 से n-1 तक के लिए करें:
    • j को 0 से m-1 तक के लिए करें:
      • val := matrix[i][j]
      • यदि val != -1, तो d[val] := d[val] + 1, dfs(i, j, matrix, val)
  • d के तत्वों को उनके मानों के आधार पर क्रमबद्ध करें
  • safe := क्रमबद्ध सूची का अंतिम तत्व
  • res := 0
  • d के प्रत्येक कुंजी-मान जोड़ी k, v के लिए करें:
    • यदि k != safe, तो res := res + v
  • 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]]

आउटपुट

2