← 返回题目列表

AtCoder · ahc054_a

A. 树人森林

中文机器翻译题面 查看原题

故事

AtCoder王国的南边有一片神秘的森林,俗称“失落的森林”,每次进入那里,路径都会改变。 据说这片森林里盛开着一种传说中的花,名叫 孤挺花光环 (通常缩写为AA),为找到它的人带来幸福。即使在今天,冒险家们仍会前来寻找这种花。

失落森林的真正本质是被称为“树人”的树怪将自己伪装成树木来迷惑冒险者。树人通过吸收失踪冒险者的魔法能量来维持生命,因此他们的目标是让冒险者尽可能长时间地留在森林中。 然而,如果冒险者未能到达AA,谣言就会传播“这朵花从未存在过”,并且没有人会再次进入森林。如果发生这种情况,树人将无法再获得魔法能量,最终会灭亡。

此外,冒险家一边探索森林一边绘制地图以避免迷路。如果树人移动到已绘制地图的位置,冒险家会意识到那不是真正的树,而是伪装的树人,并将其砍倒。必须不惜一切代价避免这种情况。

作为树人的老大,你的职责是根据冒险者的行动调整树人的位置,以确保冒险者需要更长的时间到达防空地。

问题陈述

有一片森林,由 N \times N 单元格网格。 左上角单元格的坐标是 (0, 0)。该小区位于 i 细胞下降并且 j 右侧的单元格有坐标 (i, j)。 每个单元格要么是“空单元格”,要么是“树”。以外的区域 N \times N 网格被树木包围。

细胞 (0, \lfloor \frac{N}{2} \rfloor) 是森林的入口,是一个空牢房。 传说中的花在牢房里绽放 (t_i, t_j),这也是一个空单元格。

一位冒险家进入森林寻找传说中的花朵。 冒险家有三种状态: 当前位置 和 揭示细胞,这是公开信息,并且 目的地,它是隐藏的。 假设所有未显示的单元格都是空的森林地图称为 暂定地图.

最初, 当前位置 是森林入口, 揭示细胞 仅包括该一个单元格以及该单元格之外的所有单元格 N \times N 网格,以及 目的地 未设置。 每回合,冒险家的行动都会按以下顺序处理:

  1. 如果传说中的花在 当前位置,目标达成,冒险家停止移动。
  2. 对于四个方向(上、下、左、右)中的每一个,添加到 揭示细胞 所有未公开的单元格 当前位置 直到并包括在该方向遇到的第一个“树”单元。
  3. 如果传说中的花包含在 揭示细胞,设置 目的地 到该单元格。
  4. 如果 目的地 已设置,但从当前位置无法到达 暂定地图 仅使用空单元格,取消设置 目的地.
  5. 如果 目的地 未设置或者是 揭示细胞 除了传说中的花之外,从当前位置可通过空单元格到达的未公开单元格中均匀随机选择一个单元格 暂定地图,并将其设置为 目的地 (如果不存在这样的单元格,这将导致 WA,如下所述)。
  6. 在 暂定地图,计算到的最短距离 目的地 仅使用空单元格。移动到相邻的空单元格,以缩短与目标的距离 目的地。如果存在多个这样的单元格,请按优先顺序选择一个:上、下、左、右。

作为被称为“树人”的树怪的首领,你的目标是指挥树人迷惑冒险家,并最大限度地增加到达传奇之花所需的回合数。

在每回合开始时,你可以选择任意数量的不属于 揭示细胞 并在每个中放置一个树人。 从那时起,放置树人的单元格不再被视为“空”,而是被视为“树”。树人一旦放置就无法移动。

你必须确保从森林入口到传奇之花始终至少有一条仅由空单元组成的路径。 如果不存在这样的路径,您的解决方案将导致 WA.

评分

冒险家从森林入口到达传奇之花所需的移动次数是该测试用例的绝对分数。
绝对分数越高越好。

对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{YOUR}}{\mathrm{MAX}}),其中 YOUR 是您的绝对分数,MAX 是在该测试用例中获得的所有竞争对手中的最高绝对分数。提交的分数是相对分数的总和。

最终排名将通过比赛结束后进行的系统测试进行更多的输入来确定。 在临时/系统测试中,如果您提交的测试用例产生非法输出或超出了某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MAX 计算之外。

系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。

测试用例数量

  • 临时测试:100
  • 系统测试:3000。我们将发布 种子.txt (sha256=f46e04db0ec8f80d641bbc8e166b1d2f4050a340b356acea1adce1a41a0a7fc8) 比赛结束后。

关于相关评价体系

在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MAX。

排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的绝对分数的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。

关于执行时间

每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。

输入和输出

首先,通过标准输入给出以下信息:

N t_i t_j
b_{0,0}\cdots b_{0,N-1}
\vdots
b_{N-1,0}\cdots b_{N-1,N-1}
  • N 是森林的宽度和高度并且满足 20 \leq N \leq 40.
  • (t_i, t_j) 是传说中的花的坐标,满足 0 \leq t_i, t_j \leq N - 1,保证距森林入口的曼哈顿距离至少为 5 (0, \lfloor \frac{N}{2} \rfloor).
  • b_{i,0} \cdots b_{i,N-1} 是一个长度为的字符串 N,其中 j- 第一个字符 b_{i,j} is . 如果细胞 (i, j) 是一个空单元格,并且 T 如果它是一棵树。
  • 保证每个空单元格都可以从森林入口到达 (0, \lfloor \frac{N}{2} \rfloor) 仅遍历空单元格。

接下来,重复以下过程。
在每回合开始时,冒险家的当前位置和上一回合中新显示的单元格通过标准输入以以下格式给出:

p_i p_j
n x_0 y_0 \cdots x_{n-1} y_{n-1}
  • (p_i, p_j) 是冒险家当前的位置。
  • n 是上一回合中新发现的单元格数量,并且 (x_k, y_k) 代表坐标 k-第一个这样的单元格。
  • 在第一回合, (p_i, p_j) = (0, \lfloor \frac{N}{2} \rfloor), n = 1,和 (x_0, y_0) = (0, \lfloor \frac{N}{2} \rfloor).

If (p_i, p_j) = (t_i, t_j),表示冒险家已经到达了传说之花。在这种情况下,终止循环并结束程序。
否则,让 (x_0', y_0'), \cdots, (x_{m-1}', y_{m-1}') 是本回合开始前将放置树人的单元格集合,并将以下格式输出到标准输出:

m x_0' y_0' \cdots x_{m-1}' y_{m-1}'

输出后面必须跟有新行,并且您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE.

(2025/9/21 06:00 UTC 更新) 执行时限不仅包括参赛者的解题程序,还包括评委端测试程序。 在本题设置中,求解程序很难在任意时刻终止,因此添加了以下切断输出规范,以更容易避免 TLE.

截止输出:程序可能不会输出以上述格式放置新树的单元格集,而是输出一行仅包含 -1 ,然后立即终止。 在这种情况下,后续的回合将被视为输出已被处理 m=0 直到冒险家找到传说之花为止,测试者在该处理上花费的执行时间不计入时限。

显示示例

输入生成

让 \mathrm{rand}(L, U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。

生成森林大小 N by N = \mathrm{rand}(20, 40).

从所有单元格为空开始,并使用以下过程生成树布局:
首先确定树的最大数量 K by K = \max(1, \mathrm{rand}(0, \lfloor N^2 / 6 \rfloor)).
列出 N^2 - 1 不包括森林入口的单元格按随机顺序排列为 (i_0, j_0), \cdots, (i_{N^2 - 2}, j_{N^2 - 2}),并且对于每个 k,执行以下操作:

暂时将一棵树放置在 (i_k, j_k) 并检查是否仍然可以从森林入口到达所有空单元格。
如果不是,请取消放置。
一旦放置的树木数量达到 K.

最后选择传说之花的坐标 (t_i, t_j) 从满足要求条件的空单元格中均匀随机。

工具(输入生成器、本地测试器和可视化器)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。

该工具使用的输入文件格式

用于本地测试器的输入文件遵循以下格式:

N t_i t_j
b_{0,0}\cdots b_{0,N-1}
\vdots
b_{N-1,0}\cdots b_{N-1,N-1}
q_i^0 q_j^0
\vdots
q_i^{N^2-2} q_j^{N^2-2}

条目 末尾附加的 (q_i^k, q_j^k) 代表 k- 第候选目的地。
当冒险家选择目的地时,将按此顺序遍历列表,并选择第一个满足条件的单元格。
列表 q 是通过打乱生成的 N^2 - 1 单元格不包括森林入口,按随机顺序排列。

示例解决方案 (Python)

Python 示例解决方案如下所示。 该程序会跟踪显示的细胞,但不会放置任何树人。
N, ti, tj = map(int, input().split())
b = [input() for _ in range(N)]
revealed = [[False] * N for _ in range(N)]
while True:
    pi, pj = map(int, input().split())
    parts = input().split()
    n = int(parts[0])
    xy = list(map(int, parts[1:]))
    for k in range(n):
        x = xy[2 * k]
        y = xy[2 * k + 1]
        revealed[x][y] = True
    if pi == ti and pj == tj:
        break
    print(0, flush=True)

示例输入 1

20 16 8
........T..T........
..............T.....
T...................
........T...........
...T................
.....T..............
..........T.........
....................
......T.T.........T.
....T..........T..T.
.T..T........T.....T
........T...........
....................
.....TT.............
.................T..
....................
..........T.........
............T.....T.
....................
...........T.TTT....
16 3
1 7
8 6
8 13
3 1
13 2
16 6
2 5
18 10
10 9
19 2
7 10
6 12
4 7
10 4
10 7
18 8
12 2
14 2
3 7
4 19
14 7
18 5
5 4
4 2
14 16
11 4
0 3
0 0
8 18
19 17
11 5
18 17
18 12
10 1
8 7
17 3
16 18
16 15
0 5
13 13
14 1
8 9
19 10
17 4
15 9
9 11
1 16
4 1
10 5
1 14
17 7
17 10
11 10
8 5
6 9
4 5
4 3
12 9
6 2
4 17
8 2
19 19
12 1
2 4
8 10
13 7
5 16
2 17
5 0
16 0
14 10
6 13
18 13
12 7
0 12
11 9
8 15
10 18
11 11
16 11
5 12
9 15
7 13
15 1
16 9
7 9
15 10
1 13
7 16
7 18
3 10
1 2
18 1
15 11
5 8
6 16
8 12
2 3
18 14
5 14
13 10
2 9
17 12
0 4
11 3
13 6
17 16
14 4
16 5
14 15
17 1
16 8
3 11
12 11
8 19
1 5
5 7
12 16
0 2
17 0
19 8
7 11
10 2
3 6
0 16
5 1
4 16
19 9
7 6
3 9
6 11
16 2
13 3
19 15
12 13
6 10
6 7
16 12
15 7
13 18
8 14
19 7
4 18
15 14
11 13
4 12
11 16
17 8
2 14
12 19
15 5
9 19
12 5
13 19
3 13
9 16
10 17
7 14
3 0
6 5
17 19
9 17
15 2
1 17
17 6
2 13
9 8
5 19
9 2
8 8
15 16
15 12
15 4
10 6
4 8
7 19
10 19
18 9
9 0
10 12
16 4
15 17
1 12
18 0
13 16
14 5
9 5
13 9
1 11
2 0
14 12
14 14
2 12
7 8
1 18
5 13
9 9
10 13
16 16
3 4
17 5
0 7
5 3
17 2
11 12
13 17
18 3
1 19
1 1
6 17
12 6
15 0
8 3
11 17
8 1
14 0
15 8
7 3
14 19
2 15
15 18
17 14
2 6
3 3
12 3
10 16
6 8
3 8
14 9
10 14
18 18
3 15
0 15
11 15
18 16
5 15
3 17
16 19
11 6
5 2
13 8
12 15
5 10
6 0
7 0
5 5
4 10
7 17
11 8
6 1
4 6
19 11
7 5
10 15
18 2
18 11
2 1
12 0
0 9
5 18
13 14
15 6
9 18
9 3
15 15
4 11
2 2
13 0
8 0
9 6
9 12
9 13
9 7
5 6
4 14
12 17
2 19
2 18
14 17
8 11
6 18
3 14
5 17
11 19
1 3
15 3
10 11
18 6
19 4
17 9
14 11
19 18
17 15
0 13
11 14
3 19
7 7
4 15
9 1
12 10
2 11
19 16
9 14
4 0
6 14
10 0
17 17
12 4
17 13
16 10
13 1
2 7
19 6
12 12
0 11
7 12
19 13
0 6
12 8
19 1
14 13
1 6
11 1
0 1
0 18
7 1
14 8
6 19
4 4
1 15
8 17
5 11
5 9
16 14
10 3
13 15
0 14
1 10
7 4
3 2
3 5
6 6
6 4
3 16
12 14
15 13
18 4
19 12
17 11
15 19
6 15
13 4
16 7
4 13
7 2
19 3
12 18
1 0
16 17
10 8
11 18
8 4
18 7
6 3
19 0
19 14
16 1
16 13
1 4
1 8
0 19
18 15
2 10
0 17
14 18
7 15
1 9
9 4
14 3
11 0
14 6
13 11
3 12
11 2
2 8
4 9
3 18
8 16
19 5
2 16
11 7
13 5
17 18
13 12
10 10
0 8
9 10
18 19

示例输出 1

1 1 10
0 
1 1 8
2 2 8 2 10
-1