ধরুন আমাদের একটি 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 |
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
R :=ম্যাট্রিক্সের সারি গণনা, C :=ম্যাট্রিক্সের কলাম গণনা
-
পরিদর্শন করেছেন :=একটি নতুন সেট
-
tin :=একটি নতুন মানচিত্র, নিম্ন :=একটি নতুন মানচিত্র
-
টাইমার :=0
-
bridge_pts :=একটি নতুন সেট
-
par :=একটি নতুন মানচিত্র
-
src :=একটি জোড়া (0, 0)
-
tgt :=একটি জোড়া (R − 1, C − 1)
-
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি v, parent
লাগবে -
ভি ভিজিট হিসাবে চিহ্নিত করুন
-
par[v] :=অভিভাবক, tin[v] :=টাইমার, কম[v] :=টাইমার
-
টাইমার :=টাইমার + 1
-
শিশু :=0
-
v এর প্রতিবেশীদের জন্য, করুন
-
যদি পিতামাতার মতো হয়, তাহলে
-
পরবর্তী পুনরাবৃত্তির জন্য যান
-
-
যদি পরিদর্শন করা হয়, তাহলে
-
low[v] :=সর্বনিম্ন কম[v] এবং টিন[থেকে]
-
-
অন্যথায়,
-
dfs(to, v)
-
low[v] :=সর্বনিম্ন কম[v] এবং কম[থেকে]
-
যদি low[to]>=tin[v] এবং প্যারেন্ট নাল না হয়, তাহলে
-
bridge_pts এ v যোগ করুন
-
-
শিশু :=শিশু + 1
-
-
-
যদি অভিভাবক শূন্য হয় এবং শিশু> 1 হয়, তাহলে
-
bridge_pts এ v যোগ করুন
-
-
একটি ফাংশন bfs() সংজ্ঞায়িত করুন। এটি রুট নেবে
-
প্রশ্ন :=একক উপাদান রুট সহ একটি তালিকা সহ একটি ডবল শেষ সারি
-
পরিদর্শন করেছেন :=একটি নতুন সেট এবং প্রাথমিকভাবে রুট সন্নিবেশ করান
-
যখন Q খালি নয়, করুন
-
v :=Q এর শেষ উপাদান, তারপর Q
থেকে শেষ উপাদান মুছে দিন -
v যদি tgt এর মত হয়, তাহলে
-
রিটার্ন ট্রু
-
-
v এর প্রতিবেশীর প্রতিটি w এর জন্য, do
-
যদি w পরিদর্শন না করা হয়, তাহলে
-
w চিহ্নিত করুন
-
Q
এর বাম দিকে w সন্নিবেশ করুন
-
-
-
-
রিটার্ন ফলস
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
dfs(src, null)
-
যদি tgt সমান না হয়, তাহলে
-
রিটার্ন 0
-
-
প্রতিটি জোড়ার জন্য (i, j) bridge_pts, করুন
-
ম্যাট্রিক্স[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
