एक 2D बाइनरी मैट्रिक्स दी गई है। हमें मैट्रिक्स में मौजूद कुल वर्ग सबमैट्रिक्स की संख्या खोजनी है जहां सभी तत्व 1 हैं।
उदाहरण
इनपुट मैट्रिक्स:
| 0 | 1 | 1 |
| 0 | 1 | 1 |
आउटपुट: 5
व्याख्या: एक (2×2) वर्ग और चार (1×1) वर्ग हैं।
एल्गोरिदम (डायनामिक प्रोग्रामिंग)
- यदि
matखाली है: 0 लौटाएं c := 0i0 से पंक्ति संख्या - 1 तक:j0 से स्तंभ संख्या - 1 तक:- यदि
mat[i][j] == 1:- यदि
i == 0 or j == 0:c += 1 - अन्यथा:
temp = min(mat[i-1][j-1], mat[i][j-1], mat[i-1][j]) + mat[i][j]c += tempmat[i][j] := temp
- यदि
- यदि
cलौटाएं
Python कार्यान्वयन
def solve(mat):
if mat == []:
return 0
c = 0
for i in range(len(mat)):
for j in range(len(mat[0])):
if mat[i][j] == 1:
if i == 0 or j == 0:
c += 1
else:
temp = (min(mat[i - 1][j - 1], mat[i][j - 1], mat[i - 1][j]) + mat[i][j])
c += temp
mat[i][j] = temp
return c
matrix = [
[0, 1, 1],
[0, 1, 1]
]
print(solve(matrix)) # आउटपुट: 5
इनपुट/आउटपुट
Input: [[0, 1, 1], [0, 1, 1]]
Output: 5
नोट: मूल इनपुट में [[2, 6],[3, 4],[4, 7],[5, 5]] दिखाया गया है जो बाइनरी मैट्रिक्स नहीं है। सही इनपुट ऊपर दिया गया है।