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

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है जहां 0 पानी दर्शाता है और 1 जमीन दर्शाता है। अब हमें वह जमीन ढूंढनी है जिसकी पानी से सबसे लंबी मैनहट्टन दूरी है और अंत में दूरी लौटानी है।

उदाहरण के लिए, यदि इनपुट मैट्रिक्स है:

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

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

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम मल्टी-सोर्स BFS का उपयोग करेंगे:

यदि A खाली है, तो 0 लौटाएं
R := पंक्तियों की संख्या, C := कॉलम की संख्या
distance := R x C क्रम की मैट्रिक्स, 0 से भरी हुई
q := डबल-एंडेड क्यू जिसमें वे पेयर (r, c) हों जहां matrix[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)] में:
  - यदि x और y मैट्रिक्स की रेंज में हैं और A[x][y] == 1 है:
    - A[x][y] := 0
    - distance[x][y] := distance[r][c] + 1
    - (x, y) को q के अंत में जोड़ें
प्रत्येक पंक्ति के अधिकतम तत्व वाली लिस्ट बनाएं
उस लिस्ट का अधिकतम लौटाएं

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

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] ]