# Leetcode 1036 - Escape a Large Maze

`Note:`

- Normal BFS or DFS will def TLE cuz the grid is just too big.
- Key point: As long as a point is not
`besieged`

by`blocked[i]`

, then it must have a path to`target`

. - If a
`souce`

is besiged by`blocked`

cells, then what would happen? - The
`BFS`

would only circulate within that inner area and cannot get out. It would go through every`besieged grid`

in that area. - So, if a
`BFS`

can go through more than the number of`Max Besieged grids`

, then it’s def not besieged. - Here comes the biggest question:
`How many grids can block[i] besiged ?`

. - By some math deductions, it’s like this: It used the boundaries to form the biggest area.
- Which is $1 + 2 + 3 + … + n = \frac{n*(n-1)}{2}$
- We use a
`list[]`

to contain all visited grids, after BFS ends, if it has more than`n*(n-1)/2`

elements, it means it’s not trapped. - Do BFS on both
`start -> end`

and`end -> start`

.

`Question:`

There is a `1 million`

by `1 million`

grid on an XY-plane, and the coordinates of each grid square are (x, y).

We start at the `source`

= [sx, sy] square and want to reach the `target`

= [tx, ty] square. There is also an array of blocked squares, where each `blocked`

[i] = [xi, yi] represents a blocked square with coordinates (xi, yi).

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

Return true if and only if it is possible to reach the `target`

square from the `source`

square through a sequence of valid moves.

`Example:`

1 | Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] |

`Code:`

1 | /** |