मान लीजिए कि हमारे पास 2d बाइनरी मैट्रिक्स है जहां 0 खाली सेल का प्रतिनिधित्व करता है और 1 दीवार का प्रतिनिधित्व करता है। हमें न्यूनतम संख्या वाली कोशिकाओं को खोजना होगा जिन्हें दीवार बनने की आवश्यकता है ताकि ऊपर-बाएं सेल और नीचे-दाएं सेल के बीच कोई रास्ता न हो। हम दीवारों को ऊपर-बाएं सेल और नीचे-दाएं सेल पर नहीं रख सकते हैं। हम केवल बाएँ, दाएँ, ऊपर और नीचे जा सकते हैं तिरछे नहीं।
तो, अगर इनपुट पसंद है
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 |
तो आउटपुट 2 होगा,
| 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 |
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
आर:=मैट्रिक्स की पंक्ति गणना, सी:=मैट्रिक्स की कॉलम गणना
-
विज़िट किया गया :=एक नया सेट
-
टिन:=एक नया नक्शा, कम:=एक नया नक्शा
-
टाइमर:=0
-
Bridge_pts :=एक नया सेट
-
बराबर:=एक नया नक्शा
-
src :=एक जोड़ी (0, 0)
-
tgt :=एक जोड़ी (R - 1, C - 1)
-
फ़ंक्शन को परिभाषित करें dfs() । यह वी, माता-पिता को लेगा
-
v को विज़िट किया गया के रूप में चिह्नित करें
-
par[v]:=पैरेंट, टिन[v]:=टाइमर, कम[v]:=टाइमर
-
टाइमर:=टाइमर + 1
-
बच्चे :=0
-
v के प्रत्येक पड़ोसियों के लिए, करें
-
यदि to माता-पिता के समान है, तो
-
अगले पुनरावृत्ति के लिए जाएं
-
-
अगर जाना है, तो
-
निम्न [v] :=न्यूनतम निम्न[v] और टिन[से]
-
-
अन्यथा,
-
dfs(to, v)
-
निम्न [v] :=न्यूनतम निम्न[v] और निम्न[से]
-
अगर कम [से]>=टिन[v] और पैरेंट शून्य नहीं है, तो
-
v को Bridge_pts में जोड़ें
-
-
बच्चे :=बच्चे + 1
-
-
-
यदि माता-पिता अशक्त हैं और बच्चे> 1 हैं, तो
-
v को Bridge_pts में जोड़ें
-
-
फ़ंक्शन को परिभाषित करें bfs() । यह जड़ लेगा
-
प्रश्न:=एकल तत्व रूट वाली सूची के साथ एक डबल एंडेड कतार
-
विज़िट किया गया :=एक नया सेट और प्रारंभ में रूट डालें
-
जबकि Q खाली नहीं है, करें
-
v:=Q का अंतिम तत्व, फिर Q से अंतिम तत्व को हटा दें
-
अगर v tgt के समान है, तो
-
सही लौटें
-
-
v के पड़ोसियों में प्रत्येक w के लिए, करें
-
अगर w का दौरा नहीं किया जाता है, तो
-
w को विज़िट किया गया के रूप में चिह्नित करें
-
Q के बाईं ओर w डालें
-
-
-
-
झूठी वापसी
-
मुख्य विधि से निम्न कार्य करें -
-
dfs(src, null)
-
अगर tgt बराबर नहीं है, तो
-
वापसी 0
-
-
ब्रिज_पीटी में प्रत्येक जोड़ी (i, j) के लिए, करें
-
मैट्रिक्स [i, j] :=1
-
-
अगर bfs(src) सही है, तो
-
वापसी 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], ]
आउटपुट
2
