पायथन का उपयोग करके सभी के साथ सबमैट्रिस गिनने का कार्यक्रम

मान लीजिए कि हमारे पास m x n बाइनरी मैट्रिक्स है, हमें यह पता लगाना है कि सभी सबमैट्रिस में कितने सबमैट्रिस हैं।

तो, अगर इनपुट पसंद है

1	0	1
0	1	1
0	1	1

तब आउटपुट 13 होगा क्योंकि 6 (1x1) मैट्रिक्स, 3 (2,1) मैट्रिक्स, 2 (1x2) मैट्रिक्स, 1 (3x1) मैट्रिक्स और 1 (4x4) मैट्रिक्स हैं।

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

मी :=मैट्रिक्स की पंक्ति गणना
n :=मैट्रिक्स की कॉलम संख्या
dp :=समान आकार का एक शून्य मैट्रिक्स m x n
मैं के लिए 0 से एम -1 की सीमा में, करो
- j के लिए 0 से n-1 की सीमा में, करें
  - अगर मैं 0 और मैट्रिक्स के समान है [i, j], तो
    - डीपी [आई, जे]:=1
  - अन्यथा जब मैट्रिक्स[i][j] गैर-शून्य है, तब
    - डीपी [आई, जे]:=डीपी [आई -1, जे] + 1
कुल:=0
मैं के लिए 0 से एम -1 की सीमा में, करो
- j के लिए 0 से n-1 की सीमा में, करें
  - j+1 से n की श्रेणी में k के लिए, करें
    - कुल:=कुल + न्यूनतम dp[i,j] से dp[i,k]
कुल वापसी

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

def solve(matrix):
   m = len(matrix)
   n = len(matrix[0])
   dp = [[0] * n for _ in range(m)]
   for i in range(m):
      for j in range(n):
         if i == 0 and matrix[i][j]:
            dp[i][j] = 1
         elif matrix[i][j]:
            dp[i][j] = dp[i-1][j] + 1
   total = 0
   for i in range(m):
      for j in range(n):
         for k in range(j+1, n+1):
            total += min(dp[i][j:k])
   return total
matrix = [[1,0,1],[0,1,1],[0,1,1]]
print(solve(matrix))

इनपुट

[4,6,7,8], 11