โปรแกรมนับจำนวนวิธีที่เราสามารถตัดเมทริกซ์เป็น k ชิ้นใน python

สมมติว่าเรามีเมทริกซ์ไบนารีและค่าอื่น k คุณต้องการแบ่งเมทริกซ์ออกเป็น k ชิ้น โดยให้แต่ละชิ้นมีอย่างน้อย 1 ชิ้นในนั้น แต่มีกฎบางอย่างสำหรับการตัด เราต้องปฏิบัติตามตามลำดับ:1. เลือกทิศทาง:แนวตั้งหรือแนวนอน 2. เลือกดัชนีในเมทริกซ์เพื่อตัดเป็นสองส่วน 3. ถ้าเราตัดแนวตั้ง เราไม่สามารถตัดส่วนซ้ายอีกต่อไป แต่สามารถตัดส่วนขวาต่อไปเท่านั้น 4. หากเราตัดในแนวนอน เราไม่สามารถตัดส่วนบนได้อีกต่อไป แต่สามารถตัดส่วนล่างต่อไปได้เท่านั้น เราจึงต้องหาจำนวนวิธีต่างๆ ที่จะหารเมทริกซ์ได้ หากคำตอบมีขนาดใหญ่มาก ให้คืนค่า mod ผลลัพธ์ (10^9 + 7)

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

k =2 จากนั้นผลลัพธ์จะเป็น 4 เนื่องจากเราสามารถตัดแนวตั้งสองครั้งและแนวนอนสองครั้งได้

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

• p :=10^9 + 7
• m :=จำนวนแถวของเมทริกซ์ n :=จำนวนคอลัมน์ของเมทริกซ์
• นับ :=แผนที่ว่างเปล่า
• สำหรับ i ในช่วง m - 1 ถึง 0, do
  • สำหรับ j ในช่วง n - 1 ถึง 0, do
    • นับ[i, j] :=นับ[i + 1, j] + นับ[(i, j + 1) ] - นับ[(i + 1, j + 1) ] + เมทริกซ์[i, j]
• กำหนดฟังก์ชัน f() นี่จะใช้เวลา x, y, c
• นับ :=นับ[x, y]
• ถ้า c เหมือนกับ 0 แล้ว
  • คืนค่า 1 เมื่อนับ> 0 มิฉะนั้น 0
• ตอบ :=0
• สำหรับ i ในช่วง x + 1 ถึง m - 1 ทำ
  • ถ้า 0 <นับ[(i, y)] <นับ แล้ว
    • ans :=ans + f(i, y, c - 1)
• สำหรับ j ในช่วง y + 1 ถึง n - 1 ทำ
  • ถ้า 0 <นับ[(x, j)] <นับ แล้ว
    • ans :=ans + f(x, j, c - 1)
• ส่งคืน mod p
• จากการเรียกเมธอดหลักและคืนค่า f(0, 0, k - 1)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

from collections import defaultdict
class Solution:
   def solve(self, matrix, k):
      p = 10 ** 9 + 7

      m, n = len(matrix), len(matrix[0])
      counts = defaultdict(int)
      for i in range(m)[::-1]:
         for j in range(n)[::-1]:
            counts[(i, j)] = (counts[(i + 1, j)] + counts[(i, j + 1)] - counts[(i + 1, j + 1)] + matrix[i][j])

      def f(x, y, c):
         count = counts[(x, y)]
         if c == 0:
            return 1 if count > 0 else 0

         ans = 0
         for i in range(x + 1, m):
            if 0 < counts[(i, y)] < count:
               ans += f(i, y, c - 1)
         for j in range(y + 1, n):
            if 0 < counts[(x, j)] < count:
               ans += f(x, j, c - 1)

         return ans % p
      return f(0, 0, k - 1)
     
ob = Solution()
matrix = [
   [1, 1, 0],
   [1, 0, 1],
   [1, 1, 1],
]
k = 2
print(ob.solve(matrix, k))

อินพุต

[  
[1, 1, 0],  
[1, 0, 1],  
[1, 1, 1]
], 2

ผลลัพธ์

4