कई द्वीपों को खोजने का कार्यक्रम, जहां से हम पायथन में नहीं जा सकते हैं

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है। यहां 1 भूमि का प्रतिनिधित्व करता है और 0 पानी का प्रतिनिधित्व करता है। किसी भी भूमि से हम ऊपर, नीचे, बाएँ या दाएँ जा सकते हैं लेकिन तिरछे रूप से किसी अन्य लैंड सेल में नहीं जा सकते हैं या मैट्रिक्स से बाहर जा सकते हैं। हमें उन भूमि कोशिकाओं की संख्या ज्ञात करनी है जिनसे हम मैट्रिक्स से बाहर नहीं जा सकते।

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

तो आउटपुट 4 होगा, क्योंकि बीच में 4 लैंड स्क्वेयर हैं, जहां से हम मैट्रिक्स से बाहर नहीं निकल सकते।

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

• q :=प्रत्येक पंक्ति i और कॉलम के लिए जोड़े (i, j) की एक सूची जब मैट्रिक्स [i, j] भूमि है i और j बॉर्डर इंडेक्स हैं
• आईडीएक्स:=0
• क्यू में प्रत्येक जोड़ी (x, y) के लिए, करें
  • मैट्रिक्स[x, y] :=0
• जबकि idx
• x, y:=q[idx]
• प्रत्येक (dx, dy) के लिए [(-1, 0) ,(0, -1) ,(0, 1) ,(1, 0) ] में, do
  • एनएक्स:=एक्स + डीएक्स
  • ny :=y + dy
  • यदि 0 <=nx <मैट्रिक्स की पंक्ति गणना और 0 <=ny <मैट्रिक्स की कॉलम संख्या [एनएक्स] और मैट्रिक्स [एनएक्स, एनई] 1 है, तो
    • मैट्रिक्स[एनएक्स, एनवाई] :=0
    • q के अंत में (nx, ny) डालें
• idx :=idx + 1

उदाहरण

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

def solve(matrix):
   q = [(i, j) for i in range(len(matrix)) for j in range(len(matrix[i])) if matrix[i][j] and (i == 0 or i == len(matrix) - 1 or j == 0 or j == len(matrix[i]) - 1)]
   idx = 0
   for x, y in q:
      matrix[x][y] = 0
   while idx < len(q):
      x, y = q[idx]
      for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
         nx, ny = x + dx, y + dy
         if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]:
            matrix[nx][ny] = 0
            q.append((nx, ny))
      idx += 1
   return sum(sum(row) for row in matrix)

matrix = [
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]
print(solve(matrix))

इनपुट

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

आउटपुट

4