Problem statement

https://leetcode.com/problems/escape-a-large-maze/

Solution

What we need to use in this problem that number of blocked cells is quite small. Let us run usual dfs/bfs from both source. If we have n blocked cells, it means that there can not be connected components with more than O(n^2) cells, in fact optimal case will be when it creates triangle in the corner. So if we make more than O(n^2) steps and we still can visit more cells, it means that we are not in the small connected component. The same we need to to with target: it also need to be not in small connected component. If both not in small connected components, return True, in the opposite case return False.

Complexity

It is O(n^2) for time and space, where n is the length of blocked.

Code

class Solution:
    def isEscapePossible(self, blocked, source, target):
        LIM, M = 21000, 1000000
        
        def bfs(node1, node2):
            queue = deque([node1])
            visited = set([node1])
            for b1, b2 in blocked: visited.add((b1, b2))

            while queue:
                if len(visited) >= LIM: return True
                x, y = queue.popleft()
                if (x, y) == node2: return True
                for i, j in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
                    if 0 <= i < M and 0 <= j < M and (i, j) not in visited:
                        visited.add((i, j))
                        queue.append((i, j))
                        
            return False
        
        s, t = tuple(source), tuple(target)
        return bfs(s, t) and bfs(t, s)