मान लीजिए हमारे पास m x n बाइनरी मैट्रिक्स है, हमें ढूंढना है कि कितने वर्ग सबमैट्रिक्स में सभी 1 हैं।
उदाहरण के लिए, यदि इनपुट इस तरह है:
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 |
तो आउटपुट 15 होगा, क्योंकि 10 वर्ग भुजा 1 के हैं, 4 वर्ग भुजा 2 के हैं और 1 वर्ग भुजा 3 का है। कुल वर्गों की संख्या = 10 + 4 + 1 = 15।
हल करने के चरण
यदि मैट्रिक्स में एक ही 1 है, तो
1 वापस करें
rows := मैट्रिक्स की पंक्ति संख्या
cols := मैट्रिक्स[0] की स्तंभ संख्या
result := 0
row को 0 से rows - 1 तक की रेंज में लिए करें
col को 0 से cols - 1 तक की रेंज में लिए करें
यदि row, 0 के समान है या col, 0 के समान है, तो
यदि matrix[row][col], 1 के समान है, तो
result := result + 1
अन्यथा जब matrix[row][col], 1 के समान है, तो
square := 1 + (matrix[row-1][col], matrix[row][col-1] और matrix[row-1][col-1] का न्यूनतम)
matrix[row][col] := square
result := result + square
result वापस करें
उदाहरण
def solve(matrix):
if matrix == [[1]]:
return 1
rows = len(matrix)
cols = len(matrix[0])
result = 0
for row in range(rows):
for col in range(cols):
if (row == 0 or col == 0):
if matrix[row][col] == 1:
result += 1
elif matrix[row][col] == 1:
square = min(matrix[row-1][col], min(matrix[row][col-1], matrix[row-1][col-1])) + 1
matrix[row][col] = square
result += square
return result
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
print(solve(matrix))
इनपुट
[[0,1,1,1],[1,1,1,1],[0,1,1,1]]
आउटपुट
15
