পাইথনে উপরের বাম ও নিচের ডান কোণ পৃথক করার জন্য ন্যূনতম দেওয়াল গণনা

একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে (০ = খালি, ১ = দেওয়াল)। উপরের বাম (0,0) এবং নিচের ডান (R-1,C-1) কোণার মাঝপথ বন্ধ করার জন্য ন্যূনতম কতটি খালি সেলকে দেওয়াল বানাতে হবে তা বের করতে হবে। নিজে দো কোণায় দেওয়াল দেওয়া যাবে না। চলাচল শুধু আপ, ডাউন, লেফট, রাইট।

উদাহরণ: ইনপুট ম্যাট্রিক্স → আউটপুট 2।

সমাধানের ধাপসমূহ (আর্টিকুলেশন পয়েন্ট / ব্রিজ ফাইন্ডিং + BFS)

R, C := সারি ও কলাম। src = (0,0), tgt = (R-1,C-1)।
DFS (Tarjan's Algorithm) চালিয়ে আর্টিকুলেশন পয়েন্ট (Bridge Points) bridge_pts সেটে সংগ্রহ করুন।
যদি tgt পেরেন্ট ম্যাপে না থাকে, তবে পথ নেই → রিটার্ন ০।
সব ব্রিজ পয়েন্টকে দেওয়াল (১) বানান।
BFS চালিয়ে চেক করুন src থেকে tgt পৌঁছানো যায় কিনা।
যদি যায়, তবে উত্তর ২, অন্যথায় ১।

পাইথন কোড উদাহরণ

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