Problem statement

https://binarysearch.com/problems/Walled-Off/

Solution

Quite difficult problem. The idea is the following:

  1. If we can not reach end from start, we can return 0.
  2. Find all articulation points in our graph, which we can reach from (0, 0). Notice however, that not all of them will block the path from start to end, so what we can do now is to block all these cells and check if we still can reach end point. If we can, it means that answer is 2 and it is 1 in the opposite case.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, M):
        n, m = len(M), len(M[0])
        used, tin, fup = [0]*(n*m), [-1]*(n*m), [-1]*(n*m)
        self.timer, ans = 0, set()

        def dfs(node, par = -1):
            used[node] = 1
            tin[node] = fup[node] = self.timer + 1
            self.timer += 1
            children = 0
            for child in G[node]:
                if child == par: continue
                if used[child] == 1:
                    fup[node] = min(fup[node], tin[child])
                else:
                    dfs(child, node)
                    fup[node] = min(fup[node], fup[child])
                    if fup[child] >= tin[node] and par != -1: ans.add(node)
                    children += 1
            if par == -1 and children > 1: ans.add(node)
        
        def create_graph():
            G = defaultdict(list)
            for x, y in product(range(n), range(m)):
                if M[x][y] == 1: continue
                for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0):
                    if 0 <= x + dx < n and 0 <= y + dy < m and M[x+dx][y+dy] == 0:
                        G[(x + dx)*m + y + dy] += [x * m + y]
            return G

        def bfs(root, target):
            Q, V = deque([root]), set([root])
            while Q:
                v = Q.popleft()
                if v == target: return True
                for w in G[v]:
                    if w not in V:
                        V.add(w)
                        Q.append(w)
            return False

        G = create_graph()
        if not bfs(0, m*n - 1): return 0
        dfs(0)
        for x in ans: M[x//m][x%m] = 1
        G = create_graph()
        return 2 if bfs(0, m*n - 1) else 1