โปรแกรมนับจำนวนการดำเนินการที่จำเป็นสำหรับทุกเซลล์ให้เป็นสีเดียวกันใน Python

สมมติว่าเรามีเมทริกซ์ M สองมิติ ตอนนี้ในแต่ละเซลล์มีค่าที่แสดงสีของมัน และเซลล์ที่อยู่ติดกัน (บน ล่าง ซ้าย ขวา) ที่มีสีเดียวกันจะถูกจัดกลุ่มเข้าด้วยกัน ตอนนี้ ให้พิจารณาการดำเนินการที่เราตั้งค่าเซลล์ทั้งหมดในกลุ่มเดียวให้เป็นสีบางสี จากนั้นให้หาจำนวนการดำเนินการขั้นต่ำที่จำเป็นเพื่อให้ทุกเซลล์มีสีเดียวกัน และเมื่อเปลี่ยนสีแล้วจะไม่สามารถตั้งค่าได้อีก

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถเติม 2 เป็นสีลงใน 1 แล้วเติม 3 ด้วย 1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

• หากเมทริกซ์ว่างเปล่า

  • คืนค่า 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 แล้ว

  • เมทริกซ์[i, j] :=-1

  • dfs(i, j + 1, เมทริกซ์, วาล)

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

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

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

• มิฉะนั้น

  • กลับ

• จากวิธีหลัก ให้ทำดังนี้−

• n :=จำนวนแถวของเมทริกซ์ m :=จำนวนคอลัมน์ของเมทริกซ์

• d :=แผนที่ว่างเปล่า

• สำหรับผมอยู่ในช่วง 0 ถึง n-1 ทำ

  • สำหรับ j ในช่วง 0 ถึง m-1 ให้ทำ

  • val :=matrix[i, j]

  • ถ้า val ไม่เหมือนกับ -1 แล้ว

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

  • dfs(i, j, matrix, val)

• จัดเรียงองค์ประกอบพจนานุกรมของ f ตามค่าของมัน

• ปลอดภัย :=องค์ประกอบสุดท้ายของ l

• res :=0

• สำหรับแต่ละคู่ของค่าคีย์ k และ v ของ d ทำ

  • ถ้า k ไม่เหมือนกับ safe แล้ว

  • 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