Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình đếm số lượng hoạt động cần thiết cho tất cả các ô thành cùng một màu trong Python

Giả sử chúng ta có một ma trận hai chiều M. Bây giờ trong mỗi ô chứa một giá trị đại diện cho màu của nó và các ô liền kề (trên, dưới, trái, phải) có cùng màu sẽ được nhóm lại với nhau. Bây giờ, hãy xem xét một hoạt động trong đó chúng tôi đặt tất cả các ô trong một nhóm thành một số màu. Sau đó, cuối cùng tìm số phép toán tối thiểu cần thiết để mọi ô có cùng màu. Và khi màu được chuyển đổi, nó không thể được thiết lập lại.

Vì vậy, nếu đầu vào giống như

2
2
2
2
1
1
1
1
2
3
2
1

Sau đó, đầu ra sẽ là 2, vì Chúng ta có thể điền nhóm với 2 như màu thành 1 và sau đó điền 3 với 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−

  • nếu ma trận trống, thì

    • trả về 0

  • Định nghĩa một hàm dfs (). Điều này sẽ lấy i, j, matrix, val

  • n:=số hàng của ma trận, m:=số col của ma trận

  • nếu tôi <0 hoặc i> n - 1 hoặc j <0 hoặc j> m - 1, thì

    • trở lại

  • nếu ma trận [i, j] giống -1, thì

    • trở lại

  • nếu ma trận [i, j] giống với val thì

    • ma trận [i, j]:=-1

    • dfs (i, j + 1, ma trận, val)

    • dfs (i + 1, j, ma trận, val)

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

    • dfs (i - 1, j, ma trận, val)

  • nếu không,

    • trở lại

  • Từ phương thức chính, hãy thực hiện như sau−

  • n:=số hàng của ma trận, m:=số col của ma trận

  • d:=bản đồ trống

  • đối với tôi trong phạm vi từ 0 đến n-1, hãy thực hiện

    • đối với j trong phạm vi 0 đến m-1, thực hiện

    • val:=matrix [i, j]

    • nếu val không giống -1, thì

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

    • dfs (i, j, matrix, val)

  • sắp xếp các phần tử từ điển của f dựa trên giá trị của chúng

  • safe:=phần tử cuối cùng của l

  • res:=0

  • đối với mỗi cặp giá trị khóa k và v của d, thực hiện

    • nếu k không giống như an toàn, thì

    • res:=res + v

  • trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

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

Đầu vào 

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

Đầu ra 

2