escape-a-large-maze

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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>.

We start at the <code>source = [sx, sy]</code> square and want to reach the <code>target = [tx, ty]</code> square. There is also an array of <code>blocked</code> squares, where each <code>blocked[i] = [xi, yi]</code> represents a blocked square with coordinates <code>(xi, yi)</code>.

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

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

&nbsp;
Example 1:

<pre>
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 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>

Example 2:

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

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= blocked.length &lt;= 200</code></li>
	<li><code>blocked[i].length == 2</code></li>
	<li><code>0 &lt;= xi, yi &lt; 106</code></li>
	<li><code>source.length == target.length == 2</code></li>
	<li><code>0 &lt;= sx, sy, tx, ty &lt; 106</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>

isEscapePossible

Escape a Large Maze

Depth-First Search

Breadth-First Search

Array

Hash Table

在一个 106 x 106 的网格中，每个网格上方格的坐标为 <code>(x, y)</code> 。

现在从源方格 <code>source = [sx, sy]</code> 开始出发，意图赶往目标方格 <code>target = [tx, ty]</code> 。数组 <code>blocked</code> 是封锁的方格列表，其中每个 <code>blocked[i] = [xi, yi]</code> 表示坐标为 <code>(xi, yi)</code> 的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 <code>blocked</code> 上。同时，不允许走出网格。

只有在可以通过一系列的移动从源方格 <code>source</code> 到达目标方格 <code>target</code> 时才返回 <code>true</code>。否则，返回 <code>false</code>。

 

示例 1：

<pre>
输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。</pre>

示例 2：

<pre>
输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：
因为没有方格被封锁，所以一定可以到达目标方格。
</pre>

 

提示：

<ul>
	<li><code>0 <= blocked.length <= 200</code></li>
	<li><code>blocked[i].length == 2</code></li>
	<li><code>0 <= xi, yi < 106</code></li>
	<li><code>source.length == target.length == 2</code></li>
	<li><code>0 <= sx, sy, tx, ty < 106</code></li>
	<li><code>source != target</code></li>
	<li>题目数据保证 <code>source</code> 和 <code>target</code> 不在封锁列表内</li>
</ul>