# In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.
#
# We start at the source square and want to reach the target square.  Each move, we can walk to a 4-directionally
# adjacent square in the grid that isn't in the given list of blocked squares.
#
# Return true if and only if it is possible to reach the target square through a sequence of moves.
#
#
#
# Example 1:
#
# Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
# Output: false
# Explanation:
# The target square is inaccessible starting from the source square, because we can't walk outside the grid.
# Example 2:
#
# Input: blocked = [], source = [0,0], target = [999999,999999]
# Output: true
# Explanation:
# Because there are no blocked cells, it's possible to reach the target square.
#
#
# Note:
#
# 0 <= blocked.length <= 200
# blocked[i].length == 2
# 0 <= blocked[i][j] < 10^6
# source.length == target.length == 2
# 0 <= source[i][j], target[i][j] < 10^6
# source != target
import collections


class Solution(object):
    def isEscapePossible(self, blocked, source, target):
        """
        :type blocked: List[List[int]]
        :type source: List[int]
        :type target: List[int]
        :rtype: bool
        """
        N = 999999
        if not blocked:
            return True
        blocked = set(map(tuple, blocked))

        def check(s, t):
            visited = set()
            que = collections.deque([(s[0], s[1])])
            level = 0
            while que:
                for _ in xrange(len(que)):
                    x, y = que.popleft()
                    if (x, y) == target:
                        return True
                    # bugfixed we should not add here
                    # visited.add((x, y))

                    for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                        nX, nY = x + dx, y + dy
                        if (nX, nY) not in blocked and (nX, nY) not in visited and 0 <= nX <= N and 0 <= nY <= N:
                            que.append((nX, nY))
                            visited.add((nX, nY))
                level += 1
                # if we reach the level restriction, means we traversed all blocked list and still we can move
                # in this case, we need to return true, means we could hit target
                # if while loop break, then it would not go to else
                if level == len(blocked):
                    break
            else:  # when while loop stopped, we are not able to move, but still we are not hit the target yet,
                # means the
                # blocked really block all the route from source to target, we will not able to reach target forever
                return False
            # while loop breaked , we come to here, means we are still able to find ways to break through all blocks
            # hence we are able to hit the target
            return True

        return check(source, target) and check(target, source)

    def isEscapePossible_wrong(self, blocked, source, target):
        """
        :type blocked: List[List[int]]
        :type source: List[int]
        :type target: List[int]
        :rtype: bool
        """
        N = 999999
        if not blocked:
            return True
        blackList, visited, self.minL, self.maxR, self.minT, self.maxB = set(), set(), N, 0, N, 0

        for nX, nY in blocked:
            blackList.add((nX, nY))

        def dfs(cur):
            if cur in visited:
                return False
            visited.add(cur)
            x, y = cur
            for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (1, -1)]:
                nX, nY = x + dx, y + dy
                if (nX, nY) in blackList and (nX, nY) not in visited and 0 <= nX <= N and 0 <= nY <= N:
                    self.minL, self.maxR, self.minT, self.maxB = min(self.minL, nY), max(self.maxR, nY), min(self.minT,
                                                                                                             nX), max(
                        self.maxB, nX)
                    if not dfs((nX, nY)):
                        return False

            return True

        if not dfs(blackList.pop()) and self.minT <= target[0] <= self.maxB and self.minL <= target[1] <= self.maxR:
            return False

        return True


if __name__ == '__main__':
    print Solution().isEscapePossible([[0, 1], [1, 0]], [0, 0], [0, 2])
    print Solution().isEscapePossible(
        [[691938, 300406], [710196, 624190], [858790, 609485], [268029, 225806], [200010, 188664], [132599, 612099],
         [329444, 633495], [196657, 757958], [628509, 883388]], [655988, 180910], [267728, 840949])
    print Solution().isEscapePossible([], [0, 0], [999999, 999999])
    print Solution().isEscapePossible(
        [[691938, 300406], [710196, 624190], [858790, 609485], [268029, 225806], [200010, 188664], [132599, 612099],
         [329444, 633495], [196657, 757958], [628509, 883388]], [655988, 180910], [267728, 840949])
