पायथन में पानी से सबसे लंबी दूरी की भूमि खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक द्विआधारी मैट्रिक्स है, जहां 0 पानी का प्रतिनिधित्व करता है और 1 भूमि का प्रतिनिधित्व करता है। अब हमें उस भूमि को खोजना होगा जिसमें पानी से मैनहट्टन की दूरी सबसे लंबी हो और अंत में दूरी लौटानी हो।

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

1	1	1	1
1	1	0	1
1	1	1	1
0	0	1	1

तो आउटपुट 3 होगा, क्योंकि [0,0] सेल में मैनहट्टन की पानी से दूरी 3 है।

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

अगर A खाली है, तो
- वापसी 0
R:=मैट्रिक्स की पंक्ति गणना, C:=मैट्रिक्स की कॉलम गणना
दूरी:=क्रम R x C का एक मैट्रिक्स और 0 से भरें
q :=कुछ जोड़े (r, c) के साथ एक डबल एंडेड कतार जहां r और c मैट्रिक्स की पंक्ति और स्तंभ अनुक्रमणिका हैं जहां मैट्रिक्स [r, c] 0 है
यदि q का आकार मुरझाया हुआ 0 या R * C है, तो
- वापसी -1
जबकि q खाली नहीं है, करें
- (r, c) :=q का बायां तत्व, फिर q से हटा दें
- प्रत्येक जोड़ी (x, y) के लिए [(r - 1, c) ,(r + 1, c) ,(r, c + 1) ,(r, c - 1)] में, do
  - यदि x और y मैट्रिक्स की सीमा में हैं और A[x, y] 1 है, तो
    - A[x, y] :=0
    - दूरी[x, y] :=दूरी[r, c] + 1
    - q के अंत में (x, y) डालें
res :=प्रत्येक पंक्तियों के अधिकतम तत्व वाली सूची
अधिकतम रेस लौटाएं

उदाहरण (पायथन)

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

from collections import deque
class Solution:
   def solve(self, A):
      if not A:
         return 0
      R, C = len(A), len(A[0])
      distance = [[0] * C for _ in range(R)]
      q = deque((r, c) for r in range(R) for c in range(C) if not A[r][c])
      if len(q) in (0, R * C):
         return -1
      while q:
         r, c = q.popleft()
         for x, y in [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)]:
            if 0 <= x < R and 0 <= y < C and A[x][y]:
               A[x][y] = 0
               distance[x][y] = distance[r][c] + 1
               q.append((x, y))
      return max(max(row) for row in distance)
ob = Solution()
matrix = [
   [1, 1, 1, 1],
   [1, 1, 0, 1],
   [1, 1, 1, 1],
   [0, 0, 1, 1]
]
print(ob.solve(matrix))

इनपुट

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