欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

搜索题目：逃离大迷宫

2026-06-14 分类：服务器技术 阅读(33) 评论(0)

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 前言
  • 解法一
    • 思路和算法
    • 代码
    • 复杂度分析
  • 解法二
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题：逃离大迷宫

出处：1036. 逃离大迷宫

难度

9 级

题目描述

要求

平面中有一个

10

6

×

10

6

\\texttt{10}^\\texttt{6} \\times \\texttt{10}^\\texttt{6}

106×106 的网格，网格中的每个方格有一个坐标

(x,

 

y)

\\texttt{(x, y)}

(x, y)。

从源方格

source

 

=

 

[s

x

,

 

s

y

]

\\texttt{source = [s}_\\texttt{x}\\texttt{, s}_\\texttt{y}\\texttt{]}

source = [sx​, sy​] 出发，想到达目标方格

target

 

=

 

[t

x

,

 

t

y

]

\\texttt{target = [t}_\\texttt{x}\\texttt{, t}_\\texttt{y}\\texttt{]}

target = [tx​, ty​]。数组

blocked

\\texttt{blocked}

blocked 是封锁的方格列表，其中每个

blocked[i]

 

=

 

[x

i

,

 

y

i

]

\\texttt{blocked[i] = [x}_\\texttt{i}\\texttt{, y}_\\texttt{i}\\texttt{]}

blocked[i] = [xi​, yi​] 表示坐标为

(x

i

,

 

y

i

)

\\texttt{(x}_\\texttt{i}\\texttt{, y}_\\texttt{i}\\texttt{)}

(xi​, yi​) 的方格禁止通行。

每次移动可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表

blocked

\\texttt{blocked}

blocked 中。不允许走出网格。

当且仅当可以通过一系列的移动从源方格

source

\\texttt{source}

source 到达目标方格

target

\\texttt{target}

target 时，返回

true

\\texttt{true}

true。

示例

示例 1：

输入：

blocked

 

=

 

[[0,1],[1,0]],

 

source

 

=

 

[0,0],

 

target

 

=

 

[0,2]

\\texttt{blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]}

blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] 输出：

false

\\texttt{false}

false 解释：从源方格无法到达目标方格，因为无法在网格中移动。 无法向北或者向东移动，因为方格禁止通行。 无法向南或者向西移动，因为不能走出网格。

示例 2：

输入：

blocked

 

=

 

[],

 

source

 

=

 

[0,0],

 

target

 

=

 

[999999,999999]

\\texttt{blocked = [], source = [0,0], target = [999999,999999]}

blocked = [], source = [0,0], target = [999999,999999] 输出：

true

\\texttt{true}

true 解释：因为没有方格被封锁，所以一定可以到达目标方格。

数据范围

  • 0

    ≤

    blocked.length

    ≤

    200

    \\texttt{0} \\le \\texttt{blocked.length} \\le \\texttt{200}

    0≤blocked.length≤200

  • blocked[i].length

    =

    2

    \\texttt{blocked[i].length} = \\texttt{2}

    blocked[i].length=2

  • 0

    ≤

    x

    i

    ,

     

    y

    i

    <

    10

    6

    \\texttt{0} \\le \\texttt{x}_\\texttt{i}\\texttt{, y}_\\texttt{i} < \\texttt{10}^\\texttt{6}

    0≤xi​, yi​<106

  • source.length

    =

    target.length

    =

    2

    \\texttt{source.length} = \\texttt{target.length} = \\texttt{2}

    source.length=target.length=2

  • 0

    ≤

    s

    x

    ,

     

    s

    y

    ,

     

    t

    x

    ,

     

    t

    y

    <

    10

    6

    \\texttt{0} \\le \\texttt{s}_\\texttt{x}\\texttt{, s}_\\texttt{y}\\texttt{, t}_\\texttt{x}\\texttt{, t}_\\texttt{y} < \\texttt{10}^\\texttt{6}

    0≤sx​, sy​, tx​, ty​<106

  • source

    ≠

    target

    \\texttt{source} \\ne \\texttt{target}

    source=target

  • 保证

    source

    \\texttt{source}

    source 和

    target

    \\texttt{target}

    target 不在封锁列表内

前言

判断是否可以从源方格到达目标方格，常规的做法是从源方格出发使用广度优先搜索或深度优先搜索判断是否可以到达目标方格。这道题中，网格的行数和列数是

10

6

10^6

106，因此网格中的单元格数量是

10

6

×

10

6

=

10

12

10^6 \\times 10^6 = 10^{12}

106×106=1012，该数据规模不允许直接搜索源方格和目标方格之间是否存在路径。

如果不能从源方格到达目标方格，则源方格和目标方格中至少有一个方格位于封闭区域中，且源方格和目标方格不在同一个封闭区域中。封闭区域由封锁的方格和网格边界组成（封闭区域必须包含封锁的方格，整个网格不视为封闭区域），由于封锁的方格数量不超过

200

200

200，因此可以根据封锁的方格判断源方格和目标方格是否位于封闭区域中以及是否位于同一个封闭区域中，从而判断是否可以从源方格到达目标方格。以下两种情况可以从源方格到达目标方格。

  • 存在从源方格到达目标方格的路径。

  • 源方格和目标方格都不在封闭区域中。

为了判断源方格和目标方格是否在封闭区域中，需要计算封闭区域的最大可能面积，以及分别计算从源方格和目标方格出发可以到达的方格数，判断方法如下。

  • 如果从一个方格出发可以到达的方格数超过封闭区域的最大可能面积，则该方格不在封闭区域中。

  • 如果从一个方格出发可以到达的方格数不超过封闭区域的最大可能面积，则该方格在封闭区域中。

用

n

n

n 表示封锁的方格数量。如果封闭区域的边界上有多个封锁的方格位于相同行或相同列，则可以将封锁的方格位置向封闭区域外侧方向移动，调整为对角线相邻且任意两个封锁的方格都在不同行和不同列，保持区域封闭，得到面积更大的封闭区域。为了使封闭区域的面积最大，封闭区域应位于网格的一个角落处，此时封闭区域共有

n

−

1

n – 1

n−1 行，封闭区域中的每一行分别有

1

1

1 个到

n

−

1

n – 1

n−1 个方块，封闭区域的最大面积是

n

(

n

−

1

)

2

\\dfrac{n(n – 1)}{2}

2n(n−1)​。

得到封闭区域的最大可能面积之后，即可分别计算从源方格和目标方格出发可以到达的方格数，判断是否可以从源方格到达目标方格。可以使用广度优先搜索或深度优先搜索实现。

解法一

思路和算法

如果封锁的方格数量不超过

1

1

1，则网格中一定没有封闭区域，因此一定可以从源方格到达目标方格，返回

true

\\text{true}

true。

使用广度优先搜索时，需要记录每个封锁的方格的位置，在遍历过程中维护已访问的方格。由于网格的行数和列数是

10

6

10^6

106，因此不能使用二维数组记录方格信息，而是需要使用哈希集合记录方格信息，哈希集合中记录方格的坐标的整数表示。由于每个方格的横坐标和纵坐标都在范围

[

0

,

999999

]

[0, 999999]

[0,999999] 中，因此可以将下标

(

x

,

y

)

(x, y)

(x,y) 表示成整数

x

×

10

6

+

y

x \\times 10^6 + y

x×106+y，该表示方法可以确保任意两个不同方格坐标对应的整数表示不同。

遍历数组

blocked

\\textit{blocked}

blocked，得到每个封锁的方格坐标对应的整数表示，根据封锁的方格数量计算封闭区域的最大可能面积。然后分别从源方格和目标方格执行广度优先搜索，每次广度优先搜索的结果可能有以下三种：封闭、开放、到达，每种结果的含义分别如下。

  • 封闭：从当前方格出发可以到达的方格数不超过封闭区域的最大可能面积，该方格在封闭区域中。

  • 开放：从当前方格出发可以到达的方格数超过封闭区域的最大可能面积，该方格不在封闭区域中。

  • 到达：找到从源方格到达目标方格的路径，或找到从目标方格到达源方格的路径。

从源方格执行广度优先搜索，对于每种结果，分别执行如下判断。

  • 如果结果是到达，则找到从源方格到达目标方格的路径，返回

    true

    \\text{true}

    true。

  • 如果结果是封闭，则源方格在封闭区域中且目标方格不在同一个封闭区域中，返回

    false

    \\text{false}

    false。

  • 如果结果是开放，则从目标方格执行广度优先搜索，根据目标方格搜索的结果，执行如下判断。

    • 如果结果是封闭，则目标方格在封闭区域中且源方格不在同一个封闭区域中，返回

      false

      \\text{false}

      false。

    • 如果结果是到达或开放，则由于源方格搜索的结果是开放，因此返回

      true

      \\text{true}

      true。

代码

class Solution {
static final int CLOSED = 0, OPEN = 1, REACHED = 2;
static final int BOUNDARY = 1000000;
static int[][] dirs = {{–1, 0}, {1, 0}, {0, –1}, {0, 1}};
Set<Long> blockSet = new HashSet<Long>();
int maxArea;

public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
if (blocked.length <= 1) {
return true;
}
for (int[] pos : blocked) {
blockSet.add((long) pos[0] * BOUNDARY + pos[1]);
}
maxArea = blocked.length * (blocked.length – 1) / 2;
long sourcePos = (long) source[0] * BOUNDARY + source[1];
long targetPos = (long) target[0] * BOUNDARY + target[1];
int searchStart = bfs(sourcePos, targetPos);
if (searchStart == REACHED) {
return true;
} else if (searchStart == CLOSED) {
return false;
} else {
int searchEnd = bfs(targetPos, sourcePos);
return searchEnd != CLOSED;
}
}

public int bfs(long sourcePos, long targetPos) {
Set<Long> visited = new HashSet<Long>();
visited.add(sourcePos);
Queue<Long> queue = new ArrayDeque<Long>();
queue.offer(sourcePos);
while (!queue.isEmpty()) {
long pos = queue.poll();
int row = (int) (pos / BOUNDARY), col = (int) (pos % BOUNDARY);
for (int[] dir : dirs) {
int newRow = row + dir[0], newCol = col + dir[1];
if (newRow >= 0 && newRow < BOUNDARY && newCol >= 0 && newCol < BOUNDARY) {
long newPos = (long) newRow * BOUNDARY + newCol;
if (newPos == targetPos) {
return REACHED;
}
if (!blockSet.contains(newPos) && visited.add(newPos)) {
if (visited.size() > maxArea) {
return OPEN;
}
queue.offer(newPos);
}
}
}
}
return CLOSED;
}
}

复杂度分析

  • 时间复杂度：

    O

    (

    n

    2

    )

    O(n^2)

    O(n2)，其中

    n

    n

    n 是数组

    blocked

    \\textit{blocked}

    blocked 的长度。最多执行两次广度优先搜索，每次广度优先搜索的状态数不超过

    n

    (

    n

    −

    1

    )

    2

    \\dfrac{n(n – 1)}{2}

    2n(n−1)​，因此每次广度优先搜索的时间复杂度是

    O

    (

    n

    2

    )

    O(n^2)

    O(n2)。

  • 空间复杂度：

    O

    (

    n

    2

    )

    O(n^2)

    O(n2)，其中

    n

    n

    n 是数组

    blocked

    \\textit{blocked}

    blocked 的长度。记录封锁的方格的哈希集合需要

    O

    (

    n

    )

    O(n)

    O(n) 的空间，广度优先搜索的状态数不超过

    n

    (

    n

    −

    1

    )

    2

    \\dfrac{n(n – 1)}{2}

    2n(n−1)​，记录已访问的方格的哈希集合和队列需要

    O

    (

    n

    2

    )

    O(n^2)

    O(n2) 的空间。

解法二

思路和算法

如果封锁的方格数量不超过

1

1

1，则网格中一定没有封闭区域，因此一定可以从源方格到达目标方格，返回

true

\\text{true}

true。

使用深度优先搜索时，需要记录每个封锁的方格的位置，在遍历过程中维护已访问的方格。由于网格的行数和列数是

10

6

10^6

106，因此不能使用二维数组记录方格信息，而是需要使用哈希集合记录方格信息，哈希集合中记录方格的坐标的整数表示。由于每个方格的横坐标和纵坐标都在范围

[

0

,

999999

]

[0, 999999]

[0,999999] 中，因此可以将下标

(

x

,

y

)

(x, y)

(x,y) 表示成整数

x

×

10

6

+

y

x \\times 10^6 + y

x×106+y，该表示方法可以确保任意两个不同方格坐标对应的整数表示不同。

遍历数组

blocked

\\textit{blocked}

blocked，得到每个封锁的方格坐标对应的整数表示，根据封锁的方格数量计算封闭区域的最大可能面积。然后分别从源方格和目标方格执行深度优先搜索，每次深度优先搜索的结果可能有以下三种：封闭、开放、到达，每种结果的含义分别如下。

  • 封闭：从当前方格出发可以到达的方格数不超过封闭区域的最大可能面积，该方格在封闭区域中。

  • 开放：从当前方格出发可以到达的方格数超过封闭区域的最大可能面积，该方格不在封闭区域中。

  • 到达：找到从源方格到达目标方格的路径，或找到从目标方格到达源方格的路径。

从源方格执行深度优先搜索，对于每种结果，分别执行如下判断。

  • 如果结果是到达，则找到从源方格到达目标方格的路径，返回

    true

    \\text{true}

    true。

  • 如果结果是封闭，则源方格在封闭区域中且目标方格不在同一个封闭区域中，返回

    false

    \\text{false}

    false。

  • 如果结果是开放，则从目标方格执行深度优先搜索，根据目标方格搜索的结果，执行如下判断。

    • 如果结果是封闭，则目标方格在封闭区域中且源方格不在同一个封闭区域中，返回

      false

      \\text{false}

      false。

    • 如果结果是到达或开放，则由于源方格搜索的结果是开放，因此返回

      true

      \\text{true}

      true。

代码

class Solution {
static final int CLOSED = 0, OPEN = 1, REACHED = 2;
static final int BOUNDARY = 1000000;
static int[][] dirs = {{–1, 0}, {1, 0}, {0, –1}, {0, 1}};
Set<Long> blockSet = new HashSet<Long>();
int maxArea;

public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
if (blocked.length <= 1) {
return true;
}
for (int[] pos : blocked) {
blockSet.add((long) pos[0] * BOUNDARY + pos[1]);
}
maxArea = blocked.length * (blocked.length – 1) / 2;
long sourcePos = (long) source[0] * BOUNDARY + source[1];
long targetPos = (long) target[0] * BOUNDARY + target[1];
int searchStart = dfs(sourcePos, targetPos, new HashSet<Long>());
if (searchStart == REACHED) {
return true;
} else if (searchStart == CLOSED) {
return false;
} else {
int searchEnd = dfs(targetPos, sourcePos, new HashSet<Long>());
return searchEnd != CLOSED;
}
}

public int dfs(long pos, long targetPos, Set<Long> visited) {
visited.add(pos);
if (visited.size() > maxArea) {
return OPEN;
}
boolean open = false;
int row = (int) (pos / BOUNDARY), col = (int) (pos % BOUNDARY);
for (int[] dir : dirs) {
int newRow = row + dir[0], newCol = col + dir[1];
if (newRow >= 0 && newRow < BOUNDARY && newCol >= 0 && newCol < BOUNDARY) {
long newPos = (long) newRow * BOUNDARY + newCol;
if (newPos == targetPos) {
return REACHED;
}
if (!blockSet.contains(newPos) && !visited.contains(newPos)) {
int nextSearch = dfs(newPos, targetPos, visited);
if (nextSearch == REACHED) {
return nextSearch;
} else if (nextSearch == OPEN) {
open = true;
}
}
}
}
return open ? OPEN : CLOSED;
}
}

复杂度分析

  • 时间复杂度：

    O

    (

    n

    2

    )

    O(n^2)

    O(n2)，其中

    n

    n

    n 是数组

    blocked

    \\textit{blocked}

    blocked 的长度。最多执行两次深度优先搜索，每次深度优先搜索的状态数不超过

    n

    (

    n

    −

    1

    )

    2

    \\dfrac{n(n – 1)}{2}

    2n(n−1)​，因此每次深度优先搜索的时间复杂度是

    O

    (

    n

    2

    )

    O(n^2)

    O(n2)。

  • 空间复杂度：

    O

    (

    n

    2

    )

    O(n^2)

    O(n2)，其中

    n

    n

    n 是数组

    blocked

    \\textit{blocked}

    blocked 的长度。记录封锁的方格的哈希集合需要

    O

    (

    n

    )

    O(n)

    O(n) 的空间，深度优先搜索的状态数不超过

    n

    (

    n

    −

    1

    )

    2

    \\dfrac{n(n – 1)}{2}

    2n(n−1)​，记录已访问的方格的哈希集合和递归调用栈需要

    O

    (

    n

    2

    )

    O(n^2)

    O(n2) 的空间。

赞(0)
未经允许不得转载：171主机测评 » 搜索题目：逃离大迷宫
分享到： 更多 (0)
标签：

相关推荐

评论 抢沙发

取消

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

热门标签

#人工智能(60865)#python(20513)#开发语言(17157)#java(15737)#运维(15601)#linux(15137)#大数据(14800)#服务器(13241)#算法(11908)#前端(11130)#网络(9548)#ai(9262)#数据库(9058)#c++(8289)#学习(6913)#课程设计(6888)#机器学习(6803)#区块链(5967)#OpenClaw(5399)#后端(5243)#spring boot(5075)#深度学习(5032)#c语言(4417)#毕业设计(4327)#数据结构(4233)#安全(4226)#docker(3975)#架构(3969)#javascript(3863)#大模型(3737)

热门文章

最新文章

归档

分类