पायथन में द्वीपों के बीच सबसे छोटे पुल की दूरी ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है, जहां 0 पानी दर्शाता है और 1 भूमि। एक द्वीप 4 दिशाओं में जुड़े 1 का समूह है। द्वीप या तो 0 (पानी) से घिरे होते हैं या किनारों से। हमें दो द्वीपों को जोड़ने वाले सबसे छोटे पुल की लंबाई ज्ञात करनी है।

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

तो आउटपुट 1 होगा। यह (1,0) को (1,2) बिंदुओं से जोड़ता है।

एल्गोरिदम

• row := मैट्रिक्स की पंक्तियों की संख्या, col := मैट्रिक्स के कॉलम की संख्या
• dfs() फ़ंक्शन परिभाषित करें जो i, j, s लेता है
• यदि (i, j) s में है, तो वापस लौटें
• यदि mat[i][j] == 0, तो वापस लौटें
• (i, j) को s में डालें
• चारों दिशाओं (ऊपर, नीचे, बाएं, दाएं) के लिए DFS कॉल करें
• मुख्य विधि से:
  • seen := नया सेट
  • पहला द्वीप खोजने के लिए मैट्रिक्स को पार करें और उसके सभी सेल्स को seen में जोड़ें
  • q := डबल-एंडेड क्यू
  • seen में प्रत्येक भूमि सेल के लिए, उसके आसन्न पानी के सेल्स को दूरी 1 के साथ क्यू में डालें
  • BFS चलाएं: क्यू से सेल निकालें, यदि वह दूसरे द्वीप (mat[i][j] == 1) से टकराता है तो dist - 1 वापस करें

उदाहरण

import collections
class Solution:
    def solve(self, mat):
        row = len(mat)
        col = len(mat[0])
        def dfs(i, j, s):
            if (i, j) in s: return
            if mat[i][j] == 0: return
            s.add((i, j))
            if i - 1 >= 0: dfs(i - 1, j, s)
            if i + 1 < row: dfs(i + 1, j, s)
            if j - 1 >= 0: dfs(i, j - 1, s)
            if j + 1 < col: dfs(i, j + 1, s)
        seen = set()
        for i in range(row):
            if len(seen) > 0: break
            for j in range(col):
                if mat[i][j] == 1:
                    dfs(i, j, seen)
                    break
        q = collections.deque()
        for land in seen:
            i, j = land
            if i - 1 >= 0 and mat[i - 1][j] == 0: q.append((i - 1, j, 1))
            if i + 1 < row and mat[i + 1][j] == 0: q.append((i + 1, j, 1))
            if j - 1 >= 0 and mat[i][j - 1] == 0: q.append((i, j - 1, 1))
            if j + 1 < col and mat[i][j + 1] == 0: q.append((i, j + 1, 1))
        while q:
            i, j, dist = q.popleft()
            if (i, j) in seen: continue
            seen.add((i, j))
            if mat[i][j] == 1: return dist - 1
            if i - 1 >= 0: q.append((i - 1, j, dist + 1))
            if i + 1 < row: q.append((i + 1, j, dist + 1))
            if j - 1 >= 0: q.append((i, j - 1, dist + 1))
            if j + 1 < col: q.append((i, j + 1, dist + 1))

ob = Solution()
matrix = [[0, 0, 1], [1, 0, 1], [1, 0, 0]]
print(ob.solve(matrix))

इनपुट

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

आउटपुट

1