Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python प्रोग्राम - बाइनरी मैट्रिक्स में वर्ग सबमैट्रिक्स की संख्या गिनें

एक 2D बाइनरी मैट्रिक्स दी गई है। हमें मैट्रिक्स में मौजूद कुल वर्ग सबमैट्रिक्स की संख्या खोजनी है जहां सभी तत्व 1 हैं।

उदाहरण

इनपुट मैट्रिक्स:

011
011

आउटपुट: 5

व्याख्या: एक (2×2) वर्ग और चार (1×1) वर्ग हैं।

एल्गोरिदम (डायनामिक प्रोग्रामिंग)

  1. यदि mat खाली है: 0 लौटाएं
  2. c := 0
  3. i 0 से पंक्ति संख्या - 1 तक:
    • j 0 से स्तंभ संख्या - 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 += temp
          • mat[i][j] := temp
  4. 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]] दिखाया गया है जो बाइनरी मैट्रिक्स नहीं है। सही इनपुट ऊपर दिया गया है।

  1. पायथन में दिए गए एज को शामिल करने वाले अद्वितीय पथों की संख्या गिनने का प्रोग्राम पायथन में दिए गए एज को शामिल करने वाले अद्वितीय पथों की संख्या गिनने का प्रोग्राम

    मान लीजिए हमारे पास (u, v) के रूप में एज की सूची है जो एक ट्री दर्शाती है। प्रत्येक एज के लिए हमें उन अद्वितीय पथों की कुल संख्या ज्ञात करनी है जिनमें वह एज शामिल है, उसी क्रम में जैसे इनपुट में दिया गया है। उदाहरण के लिए, यदि इनपुट है edges = [[0, 1],[0, 2],[1, 3],[1, 4]], तो आउटपुट [6, 4, 4, 4] ह

  1. मैट्रिक्स में पूरी तरह से घिरे हुए द्वीपों की संख्या गिनने का पायथन प्रोग्राम मैट्रिक्स में पूरी तरह से घिरे हुए द्वीपों की संख्या गिनने का पायथन प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। जहां 1 भूमि दर्शाता है और 0 पानी दर्शाता है। जैसा कि हम जानते हैं एक द्वीप 1 का समूह है जो एक साथ जुड़े हुए हैं जिसकी परिधि पानी से घिरी हुई है। हमें पूरी तरह से घिरे हुए द्वीपों की संख्या ढूंढनी है। उदाहरण के लिए, यदि इनपुट इस तरह है: तो आउटपुट 2 होगा,

  1. पायथन प्रोग्राम: लगातार 1 के बिना बाइनरी स्ट्रिंग्स की संख्या गिनें पायथन प्रोग्राम: लगातार 1 के बिना बाइनरी स्ट्रिंग्स की संख्या गिनें

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें एक धनात्मक पूर्णांक N दिया गया है, हमें लंबाई N की सभी संभावित अलग बाइनरी स्ट्रिंग्स गिननी हैं जिनमें लगातार 1 न हों। उदाहरण # स्ट्रिंग्स की संख्या गिनें def countStrings(n): a = [0 for i in range(n)] b = [0 for i in r