पायथन में ऊपरी-बाएं और नीचे-दाएं सेल को विभाजित करने के लिए आवश्यक दीवारों की संख्या गिनने का प्रोग्राम

मान लीजिए हमारे पास एक 2D बाइनरी मैट्रिक्स है जहां 0 खाली सेल दर्शाता है और 1 दीवार दर्शाता है। हमें उन न्यूनतम सेल्स की संख्या ज्ञात करनी है जिन्हें दीवार बनाने की आवश्यकता है ताकि ऊपरी-बाएं सेल और नीचे-दाएं सेल के बीच कोई पथ न रहे। हम ऊपरी-बाएं सेल और नीचे-दाएं सेल पर दीवार नहीं लगा सकते। हम केवल बाएं, दाएं, ऊपर और नीचे जा सकते हैं, विकर्ण नहीं।

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

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

तो आउटपुट 2 होगा।

हल करने के चरण

R := मैट्रिक्स की पंक्तियों की संख्या, C := मैट्रिक्स के स्तंभों की संख्या
visited := एक नया सेट
tin := एक नया मैप, low := एक नया मैप
timer := 0
bridge_pts := एक नया सेट
par := एक नया मैप
src := एक जोड़ी (0, 0)
tgt := एक जोड़ी (R - 1, C - 1)
dfs() फ़ंक्शन परिभाषित करें। यह v, parent लेगा
- v को विज़िटेड के रूप में चिह्नित करें
- par[v] := parent, tin[v] := timer, low[v] := timer
- timer := timer + 1
- children := 0
- v के प्रत्येक पड़ोसी to के लिए, करें
  - यदि to, parent के समान है, तो अगले इटरेशन पर जाएं
  - यदि to विज़िटेड है, तो low[v] := low[v] और tin[to] का न्यूनतम
  - अन्यथा, dfs(to, v), low[v] := low[v] और low[to] का न्यूनतम
  - यदि low[to] >= tin[v] और parent null नहीं है, तो v को bridge_pts में जोड़ें
  - children := children + 1
- यदि parent null है और children > 1, तो v को bridge_pts में जोड़ें
bfs() फ़ंक्शन परिभाषित करें। यह root लेगा
- Q := root वाले सिंगल एलिमेंट सूची के साथ एक डबल एंडेड क्यू
- visited := एक नया सेट और प्रारंभ में root डालें
- जब तक Q खाली नहीं है, करें
  - v := Q का अंतिम तत्व, फिर Q से अंतिम तत्व हटाएं
  - यदि v, tgt के समान है, तो True लौटाएं
  - v के प्रत्येक पड़ोसी w के लिए, करें
    - यदि w विज़िटेड नहीं है, तो w को विज़िटेड के रूप में चिह्नित करें और Q के बाएं में डालें
- False लौटाएं
मुख्य विधि से निम्नलिखित करें:
- dfs(src, null)
- यदि tgt, par में नहीं है, तो 0 लौटाएं
- bridge_pts में प्रत्येक जोड़ी (i, j) के लिए, matrix[i, j] := 1 करें
- यदि bfs(src) true है, तो 2 लौटाएं
- 1 लौटाएं

उदाहरण

from collections import deque

class Solution:
    def solve(self, matrix):
        R = len(matrix)
        C = len(matrix[0])
        def get_neighbors(i, j):
            for ii, jj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == 0:
                    yield ii, jj
        visited = set()
        tin = {}
        low = {}
        timer = 0
        bridge_pts = set()
        par = {}
        src = (0, 0)
        tgt = (R - 1, C - 1)
        def dfs(v, parent):
            nonlocal timer
            visited.add(v)
            par[v] = parent
            tin[v] = timer
            low[v] = timer
            timer += 1
            children = 0
            for to in get_neighbors(*v):
                if to == parent:
                    continue
                if to in visited:
                    low[v] = min(low[v], tin[to])
                else:
                    dfs(to, v)
                    low[v] = min(low[v], low[to])
                    if low[to] >= tin[v] and parent is not None:
                        bridge_pts.add(v)
                    children += 1
            if parent is None and children > 1:
                bridge_pts.add(v)
        def bfs(root):
            Q = deque([root])
            visited = set([root])
            while Q:
                v = Q.pop()
                if v == tgt:
                    return True
                for w in get_neighbors(*v):
                    if w not in visited:
                        visited.add(w)
                        Q.appendleft(w)
            return False
        dfs(src, None)
        if tgt not in par:
            return 0
        for i, j in bridge_pts:
            matrix[i][j] = 1
        if bfs(src):
            return 2
        return 1

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

इनपुट

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