पायथन में बम विस्फोट के बाद सुरक्षित स्थानों की संख्या गिनने का प्रोग्राम

एक 2D बाइनरी मैट्रिक्स दिया गया है जहां 1 बम दर्शाता है और 0 खाली सेल। जब बम फटता है, तो उसकी पूरी पंक्ति और स्तंभ क्षतिग्रस्त हो जाते हैं। उन सेल की संख्या गिनें जहां खड़े होने पर कोई नुकसान नहीं होगा (यानी न तो पंक्ति में बम है न स्तंभ में)।

उदाहरण

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

[[1, 1, 0],
 [0, 0, 0],
 [0, 0, 0]]

आउटपुट: 2

सुरक्षित सेल: (1,2) और (2,2) - तीसरे स्तंभ की दूसरी और तीसरी पंक्ति।

एल्गोरिदम

1. दो बूलियन सरणी बनाएं: row_has_bomb (आकार = पंक्तियाँ), col_has_bomb (आकार = स्तंभ)।
2. मैट्रिक्स को पार करें: यदि matrix[i][j] == 1, तो row_has_bomb[i] = True और col_has_bomb[j] = True सेट करें।
3. फिर से पार करें: यदि row_has_bomb[i] == False और col_has_bomb[j] == False, तो काउंटर बढ़ाएं।
4. काउंटर वापस करें।

पायथन कार्यान्वयन

class Solution:
    def solve(self, matrix):
        if not matrix:
            return 0
        rows = len(matrix)
        cols = len(matrix[0])
        
        row_has_bomb = [False] * rows
        col_has_bomb = [False] * cols
        
        # बम वाली पंक्तियों और स्तंभों को चिह्नित करें
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == 1:
                    row_has_bomb[i] = True
                    col_has_bomb[j] = True
        
        # सुरक्षित सेल गिनें
        safe = 0
        for i in range(rows):
            for j in range(cols):
                if not row_has_bomb[i] and not col_has_bomb[j]:
                    safe += 1
        return safe

# परीक्षण
ob = Solution()
matrix = [
    [1, 1, 0],
    [0, 0, 0],
    [0, 0, 0]
]
print(ob.solve(matrix))  # 2

समय जटिलता

• O(m × n) समय, O(m + n) स्थान।
• दो पास: एक चिह्नित करने के लिए, एक गिनने के लिए।

वैकल्पिक: सेट का उपयोग

bomb_rows = {i for i, row in enumerate(matrix) for j, val in enumerate(row) if val == 1}
bomb_cols = {j for i, row in enumerate(matrix) for j, val in enumerate(row) if val == 1}
safe = sum(1 for i in range(rows) for j in range(cols) if i not in bomb_rows and j not in bomb_cols)