当前位置:首页 > 搜索 > 广度优先搜索 > 正文
洛谷P7473重力球[2021NOIOnline]
1149+

题目大意:两个小球在“迷宫”里,我们可以将迷宫向上下左右四个方向倾斜,小球会随着重力往下掉到障碍物,至少操作多少次可以掉到一起?

题目描述

“重力球”游戏在一块 的正方形区域中进行,记从上往下第 行,从左往右第 列的位置为

正方形区域中存在 个障碍,第 个障碍占据位置 ,此外,正方形区域的边界外都是障碍。

现在有两个小球,位置分别是 ,在游戏中你可以进行如下操作:

  • 指定上、下、左、右中的一个方向,将重力方向“切换”为这个方向。此时两个小球会同时向这个方向移动,直到碰到障碍。

你要用最少的操作次数使得两个小球到达同一个位置。

现有 局游戏,每局游戏中只有小球的初始位置不同,而障碍位置是不变的,你需要对每局游戏都求出最小操作次数,或报告无解。

输入格式

第一行包含三个整数 ,分别表示矩形区域大小,障碍个数和游戏局数。

接下来 行,每行包含两个整数 ,表示位置 上有一个障碍。数据保证所有障碍所处的位置互不相同。

接下来 行,每行四个整数 ,表示一局游戏中两个小球的初始位置,保证初始位置不存在障碍。

输出格式

输出共 行,第 行输出一个整数表示第 局游戏需要的最小操作次数,如果无解则输出 -1

输入输出样例

输入 #1
4 4 3
2 2
2 4
3 2
4 4
1 3 4 3
2 1 2 1
1 2 3 4
输出 #1
1
0
3

说明/提示

样例 解释

该样例中障碍分布如图中红叉所示。

第一组询问中只需将重力改向上(或改向下)即可使两球同时到达。

第二组询问中两球已经在同一位置故不需操作。

第三组询问中改变3 次重力的方向,依次改为向左、向下、向左,小球移动路线分别如图中粉色、橙色、棕色线所示:

数据范围与提示

对于 的数据:

对于 的数据:

对于另外 的数据:

对于 的数据:

解题思路

显然,搜索即可!

程序实现

深搜记忆化:dfs(x, y, s, t, z)表示两个球分别在(x, y)和(s, t)的操作次数是z,爆搜记忆化可得至少20分。

深搜改广搜可得至少50分:

因为障碍物很少,小球停在的位置很少,所以我们可以记录停在障碍物的哪个方向,代替小球的位置,节省空间。优化记忆化数组,开得下空间即可获得80分,因为Q=1很小!

注意:f[i][j][k]表示两个小球分别在障碍物i和障碍物j的k^1方向,边界的方向只会用到一个,大部分空间都是用不到的,所以用逐个赋值代替memset,速度快一些。

另外,在找下一个障碍物的时候,经常会重复找,我们可以记忆化,下次直接返回之前记录的位置。总的时间复杂度是:$O(Q * n * (m+n))$。(上一个代码时间复杂度一样,只是超空间)

多组询问,通常都是预处理答案,O(1)回答。起点不一样,走到每个位置的步数就不一样。但是从终点往回走的步数,肯定是一样的。所以,我们可以从终点往回走。

怎么往回走?f[i][j][k]表示从方向k到达障碍物i和j,那么我们可以在k^1方向找前驱,特点是这个方向的两边有障碍物,两两组合即是前驱。会很多吗?不超过状态数量的4倍!因为顺着过来的时候,只能往四个方向走。

但是,在查找障碍物的时候,会重复找,需要记忆化,不记忆化会超时。

最后,我们看一下起点能到的下一个位置需要多少步即可。

预处理复杂度:O(m*m*n)

询问回答复杂度:O(Q*n)

洛谷P7473重力球[2021NOIOnline]:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!