故事
魔王高桥收到消息称英雄青木正在接近他的城堡。
为了在英雄登基之前争取尽可能多的时间,魔王决定通过安装连动的门和开关来翻新城堡。
然而,由于魔王的军队已经被一名为英雄工作的间谍渗透进来,整修计划被他完全知道了。 而且,英雄非常聪明,如果王位可以到达,他会用尽可能少的行动到达它。
作为魔王最有能力的下属之一,你被要求制定一个尽可能长时间拖延英雄的改造计划。

问题陈述
有一座魔王城堡,由 N\times N 细胞。 让 (0,0) 是左上角单元格的坐标,让 (i,j) 表示单元格 i 细胞向下并且 从那里右侧的 j 单元格。
每个单元格要么是空单元格 . 或障碍物 #。
外的所有细胞 N\times N 网格被视为障碍物。
细胞 所有整数对的 (0,0) 包含入口和单元格 (N-1,N-1) 包含王座。 这两个单元格都是空单元格。
在英雄进入城堡之前,您可以安装 门 和 开关 城堡内。
门
有 2K 类型 门,编号 0,1,\ldots,2K-1。 此后,一扇类型的门 g 将被简单地称为 门 g.
两个正交相邻的单元之间可以安装门,并且最多 M 门可全部安装。 相同的两个牢房之间最多可以安装一扇门。 可以安装多扇相同类型的门。
开关
有 K 种 开关,编号 0,1,\ldots,K-1。 此后,一种类型的转变 k 将被简单地称为 开关 k.
每个单元最多可以安装一个交换机。 不同小区中可以安装多个相同类型的交换机。 也可能有一些开关根本没有安装。 开关也可以安装在入口处 (0,0) 和王座 (N-1,N-1).
门和开关之间的联动
对于每个 k=0,1,\ldots,K-1,门 2k 和门 2k+1 由开关控制 k。 所有同一类型的门具有相同的开/关状态。
最初,门 2k 已打开,并且门 2k+1 已关闭。
每次切换 k 按下,门的开/关状态 2k 和门 2k+1 已交换。 也就是说,切换时 k 已被按偶数次,门 2k 已打开,门已打开 2k+1 已关闭。 切换时 k 已被按奇数次,门 2k 已关闭并且门 2k+1 已打开。
门可以安装在单元和障碍单元之间,但通过这样的门进行移动是不可能的。 障碍物单元上可以安装开关,但是不能按下这样的开关。
英雄的行动
城堡改造完成后,英雄从入口进入 (0,0)。 在每一回合中,英雄可以选择并执行以下两个动作之一。
- 移动到正交相邻的空单元格。但是,如果当前单元格和目标单元格之间有一扇门,并且该门关闭,则英雄无法朝该方向移动。
- 如果当前单元格上有开关,请按下该开关。
即使当前单元格上有开关,英雄也不一定必须按下它。 英雄可以在不按下开关的情况下移动到相邻的单元格。
英雄知道你安装的门和开关的整个位置。 如果王座是可以到达的,英雄就会用尽可能少的动作到达王位。
你的目标是最大化英雄从入口到达王座所需的最少动作数量。
补充:英雄的最低动作次数
对于给定的输出更新计划,最小操作数 T 可以通过执行广度优先搜索来计算,其状态包括当前位置,并且对于每个开关 k、开关次数奇偶校验 k 已被按下。
最多有 N^2 可能的当前位置,并且开关的状态可以表示为 K 位,给予 2^K 可能性。 因此, T 可以计算为 O(2^K N^2) 时间。
以下是 python 中用于计算最小操作数的示例实现。
from collections import deque
def calc_T(N, K, c, door_h, door_v, switch):
"""
N: board size
K: number of switch kinds
c: map. c[i][j] is either '.' or '#'
door_h: doors in the vertical direction. door_h[i][j] is the type of the door between (i,j) and (i+1,j). -1 if there is no door
door_v: doors in the horizontal direction. door_v[i][j] is the type of the door between (i,j) and (i,j+1). -1 if there is no door
switch: switch[i][j] is the kind of the switch placed on cell (i,j). -1 if there is no switch
Returns:
The minimum number of actions required to reach the throne (N-1,N-1) from the entrance (0,0).
Returns 0 if it is unreachable.
"""
def is_open(g, mask):
"""Returns whether the door of type g is open in state mask."""
if g == -1:
return True
k = g // 2
return ((mask >> k) & 1) == (g & 1)
dist = [[[-1] * N for _ in range(N)] for _ in range(1 << K)]
dist[0][0][0] = 0
que = deque()
que.append((0, 0, 0))
while que:
mask, i, j = que.popleft()
d = dist[mask][i][j]
if (i, j) == (N - 1, N - 1):
return d
# Action 1: Move to an adjacent empty cell
for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
ni, nj = i + di, j + dj
if not (0 <= ni < N and 0 <= nj < N):
continue
if c[ni][nj] == '#':
continue
if di == 1:
g = door_h[i][j]
elif di == -1:
g = door_h[ni][nj]
elif dj == 1:
g = door_v[i][j]
else:
g = door_v[ni][nj]
if not is_open(g, mask):
continue
if dist[mask][ni][nj] == -1:
dist[mask][ni][nj] = d + 1
que.append((mask, ni, nj))
# Action 2: Press the switch on the current cell
s = switch[i][j]
if s != -1:
nmask = mask ^ (1 << s)
if dist[nmask][i][j] == -1:
dist[nmask][i][j] = d + 1
que.append((nmask, i, j))
return 0
评分
对于你输出的改造计划,英雄能否登上王座 (N-1,N-1) 从入口处 (0,0) 在有限数量的动作中,让 T 是执行此操作所需的最少操作数。 在这种情况下,您将获得以下分数。
\[ \mathrm{round}\left(10^6\times \log_2 \frac{T}{N}\right) \]
如果英雄无法登上王座,分数将为 1.
有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出。
N M K
c_0
\vdots
c_{N-1}
- 在所有测试用例中,电路板尺寸 N 固定为 20.
- 在所有测试用例中,可以安装的最大门数, M,固定为 50.
- 在所有测试用例中,开关种类的数量, K,固定为 10.
- c_i 是一个长度为 N,及其 j- 第一个字符 c_{i,j} is
.如果细胞 (i,j) 是一个空单元格,并且#如果它是障碍物。 - c_{0,0}=c_{N-1,N-1}=
.. - 保证每个空单元格都可以从入口到达 (0,0) 仅通过空单元格。
输出
首先,让 D 是要安装的门的数量,并按以下格式将门的位置输出到标准输出。
D
d_0 i_0 j_0 g_0
\vdots
d_{D-1} i_{D-1} j_{D-1} g_{D-1}
的 a第门由其方向表示 d_a,坐标 (i_a,j_a)和门类型 g_a.
- If d_a=0,安装门 g_a 单元格之间 (i_a,j_a) 和细胞 (i_a+1,j_a).
- If d_a=1,安装门 g_a 单元格之间 (i_a,j_a) 和细胞 (i_a,j_a+1).
输出必须满足以下条件。
- 0\leq D\leq M
- 对于每扇门, d_a 为 0 或 1。
- 对于每扇门, 0\leq g_a<2K 成立。
- If d_a=0, 0\leq i_a<N-1 和 0\leq j_a<N 按住。
- If d_a=1, 0\leq i_a<N 和 0\leq j_a<N-1 按住。
- 请勿在相同的两个牢房之间安装多个门。
然后,让 S 是要安装的交换机数量,并按以下格式输出交换机的位置。
S
p_0 q_0 s_0
\vdots
p_{S-1} q_{S-1} s_{S-1}
的 b-第一个开关安装在电池上 (p_b,q_b),其种类是 s_b.
输出必须满足以下条件。
- 0\leq S\leq N^2
- 对于每个开关, 0\leq p_b,q_b<N 成立。
- 对于每个开关, 0\leq s_b<K 成立。
- 请勿在同一单元上安装多个开关。
输入生成
N=20, M=50,和 K=10 已修复。
首先,从所有单元格都是空单元格开始。 安排 N^2-2 细胞以外的细胞 (0,0) 和 (N-1,N-1) 以随机顺序排列,并按如下顺序处理它们。
令目标单元格为 (i,j)。 如果单元格的 4 个正交相邻单元格中至少有 3 个 (i,j) 是障碍细胞,跳过该细胞的过程。 细胞外的 N\times N 网格被视为障碍物。 否则,暂时更换单元格 (i,j) 进入障碍物。 如果此更改使所有空单元格断开连接,请更改单元格 (i,j) 回到空单元格中。 否则,离开单元格 (i,j) 作为障碍。
接下来,按随机顺序排列所有障碍单元,并按如下顺序处理它们。
令目标单元格为 (i,j)。 如果 cell 的 4 个正交相邻单元格中至少有一个 (i,j) 是一个空单元格,请更改单元格 (i,j) 进入空单元格。 一旦障碍单元变为空单元的次数达到 N,终止此进程。
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。