Pythonで行列をk個にカットできる方法の数を数えるプログラム

バイナリ行列と別の値kがあるとします。行列をk個の部分に分割して、各部分に少なくとも1つの1が含まれるようにします。ただし、カットにはいくつかのルールがあります。順番に従う必要があります。1.方向を選択します：垂直または水平2.マトリックス内のインデックスを選択して2つのセクションにカットします。 3.縦に切ると、左の部分はカットできなくなり、右の部分しかカットできなくなります。 4.水平にカットすると、上部をカットできなくなり、下部のみをカットし続けることができます。したがって、マトリックスを分割するためのさまざまな方法を見つける必要があります。答えが非常に大きい場合は、結果mod（10 ^ 9 + 7）を返します。

したがって、入力が次のような場合

k =2の場合、垂直方向に2回、水平方向に2回カットできるため、出力は4になります。

これを解決するには、次の手順に従います-

• p：=10 ^ 9 + 7
• m：=行列の行数、n：=行列の列数
• counts：=空のマップ
• m-1から0の範囲のiの場合、実行
  • n-1から0の範囲のjの場合、do
    • counts [i、j]：=counts [i + 1、j] + counts [（i、j + 1）]-counts [（i + 1、j + 1）] + matrix [i、j]
• 関数f（）を定義します。これにはx、y、cが必要です
• count：=counts [x、y]
• cが0と同じ場合、
  • カウント>0の場合は1を返し、それ以外の場合は0を返します
• ans：=0
• x +1からm-1の範囲のiの場合、do
  • if 0
  • ans：=ans + f（i、y、c --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