<p>There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are <code>(x, y)</code>.</p>

<p>We start at the <code>source = [s<sub>x</sub>, s<sub>y</sub>]</code> square and want to reach the <code>target = [t<sub>x</sub>, t<sub>y</sub>]</code> square. There is also an array of <code>blocked</code> squares, where each <code>blocked[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> represents a blocked square with coordinates <code>(x<sub>i</sub>, y<sub>i</sub>)</code>.</p>

<p>Each move, we can walk one square north, east, south, or west if the square is <strong>not</strong> in the array of <code>blocked</code> squares. We are also not allowed to walk outside of the grid.</p>

<p>Return <code>true</code><em> if and only if it is possible to reach the </em><code>target</code><em> square from the </em><code>source</code><em> square through a sequence of valid moves</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
<strong>Output:</strong> false
<strong>Explanation:</strong> The target square is inaccessible starting from the source square because we cannot move.
We cannot move north or east because those squares are blocked.
We cannot move south or west because we cannot go outside of the grid.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> blocked = [], source = [0,0], target = [999999,999999]
<strong>Output:</strong> true
<strong>Explanation:</strong> Because there are no blocked cells, it is possible to reach the target square.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= blocked.length &lt;= 200</code></li>
	<li><code>blocked[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt; 10<sup>6</sup></code></li>
	<li><code>source.length == target.length == 2</code></li>
	<li><code>0 &lt;= s<sub>x</sub>, s<sub>y</sub>, t<sub>x</sub>, t<sub>y</sub> &lt; 10<sup>6</sup></code></li>
	<li><code>source != target</code></li>
	<li>It is guaranteed that <code>source</code> and <code>target</code> are not blocked.</li>
</ul>

class Solution:
    def bfs(self,start_loc,target,blocked):
        
        que=[start_loc];visited=set()
        visited.add(tuple(start_loc))
        dis=0
        while que:
            #print('dis:',dis)
            #print('que:',que)
            new_que=[]
            for nod in que:
                if nod==target:return True 
                x,y=nod
                for nb in [[-1,0],[1,0],[0,-1],[0,1]]:
                    nx,ny=x+nb[0],y+nb[1]
                    if 0<=nx<10**6 and 0<=ny<10**6 and (nx,ny) not in visited and [nx,ny] not in blocked:
                        visited.add((nx,ny))
                        new_que.append([nx,ny])
                        dis=max(dis,abs(nx-start_loc[0]),abs(ny-start_loc[1]))
            #dis+=1
            que=new_que
            if dis>200:break 
        print('dis:',dis)
        return dis>200


    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
        # since blocked size only 200, 
        # if from start it can reach a distance larger than 200 for either direction, then there's no large enough loop to block start point
        no_block_in_source=self.bfs(source,target,blocked)
        no_block_in_target=self.bfs(target,source,blocked)
        return no_block_in_source and no_block_in_target
34000