UOJ Logo Universal Online Judge

UOJ

#215. 【UNR #1】果冻运输

统计

本题为提交答案题,请注意比赛中途提交上去后,对于每个测试点如果有分就会显示该测试点满分,比赛完后会进行重测给出真实的分数,请特别注意!

九条可怜是一个可爱的男孩子。

九条可怜在一家果冻生产厂家工作。这个果冻厂专门生产 $1\text{米} \times 1\text{米} \times 1\text{米}$ 的巨型果冻,在果冻生产出来以后,他们会把果冻装到一个 $1\text{米} \times n\text{米} \times m\text{米}$ 大小的集装箱中用卡车运走。

这个果冻厂生产的果冻有一个特点:一旦两个同类型果冻的一个面贴合在了一起,那么静置几秒之后这两个果冻就会粘在一起无法拉开。不同类型的果冻由于切面纹理不同所以并不会粘连。

由于果冻数量多起来之后切合面是平方级别增长的,到时候切开就会特别麻烦。所以在集装箱中还有一些用来将果冻隔开的块状物,每个块状物是由大小为 $1\text{米} \times 1\text{米} \times 1\text{米}$ 的立方体拼起来得到的。

块状物也分为已经固定的和尚未固定的两种,已经固定的表示这个块已经和两边的墙壁相连无法移动,而尚未固定的则可以和果冻一样被推动和掉落。

由于某些切面可能已经老化,所以初始状态下一个果冻可能和墙壁或者另一个块状物粘连。

九条可怜的工作是检查将要出发的卡车,使得卡车内部装货的位置尽量稳定,假如果冻过于分散,那么运输过程中的颠簸可能会影响品质。

最近,果冻厂新招了一批临时工,所以果冻的摆放非常杂乱,九条可怜需要尽量减少果冻形成的连通块的个数来保持稳定(由于果冻和墙壁之间的连接不够稳定,连通块只计算相同颜色的果冻之间相连的边)。显然,能够达成的最少连通块个数一定等于颜色数。

为了帮助九条可怜解决这个问题,公司为九条可怜分配了一个得力助手:海灵吨。

每次,海灵吨可以选择一个连通块,将它向左或向右推 $1$ 米。在推的过程中,所有“挡路的”连通块也会被向同一个方向推 $1$ 米。

当然,由于海灵吨并没有办法推动一个固定方块(包括和一个固定方块连通的方块),假如某一个操作中需要推动一个固定方块,那么这一个操作就是不合法的。

在这些方块都移动了 $1$ 米之后,所有的方块会开始掉落。所有掉落完成之后就会进入静置时间,任何相邻的相同类型的果冻在这时就会被粘连形成一个大的连通块。

为了让海灵吨节省体力,九条可怜想知道,将这些块合并成最小块数的情况下最少需要多少次操作。

输入格式

所有输入数据 C1.in~C20.in 见数据下载。 输入的第一行包含两个正整数 $n, m$,含义同题面描述。

随后 $2n-1$ 行,每行 $2m-1$ 个字符,表示初始状态。对于第 $x$ 行第 $y$ 个字符:

  1. 假如 $x$ 是奇数且 $y$ 是奇数:这个格子代表一个方块,0 代表已经固定的块状物,9 代表尚未固定的块状物,18 代表不同颜色的果冻,. 代表这个格子是空的。
  2. 假如 $x$ 是偶数且 $y$ 是偶数:这个格子是一个空格。
  3. 否则,字符为 |-,表示相邻的两个格子之间是否被粘连。

下一行包含两个空格分隔的整数 $a_1,a_2$,用途将在后面提到。

输出格式

针对给定的 20 个输入文件 C1.in~C20.in,你需要分别提交你的输出文件 C1.out~C20.out。

输出文件每行使用三个数 $x,y,z$ 表示一个操作,其中 $x,y$ 表示需要移动的位置的坐标(即从左下角开始向右移动 $x-1$ 步后向上移动 $y-1$ 步到达的位置),$z$ 表示推动的方向($0$ 表示向左,$1$表 示向右)。

样例

input

4 7
0 1 2-2 . 1-0
|           |
0-0-0 . . 0-0
|           |
0 . . 9-9 2 0
|           |
0-0-0-0-0-0-0
0 0

output

6 2 0
2 4 1
3 4 1
4 4 1

评分方式

对于每组数据,我们设置了 $2$ 个评分参数 $a_1,a_2$,并且已经在输入文件中给出。

对于每个测试点,若你有一步的输出不合法,或者你最终状态下的 $\text{块数} > \text{颜色数}+1$ 得 $0$ 分,否则设你使用的操作数为 $x$,我们给出的参考解为$y$,那么:

  1. 如果 $\text{块数} = \text{颜色数}+1$,得 $1$ 分;
  2. 否则,如果 $x \leq y$,得 $5$ 分;
  3. 否则,如果 $x \leq y+a_1$,得 $4$ 分;
  4. 否则,如果 $x \leq y+a_2$,得 $3$ 分;
  5. 否则,得$2$分。

如何测试你的输出

本题有附加文件 checker.cpp,是一个本地的校验器的 C++ 代码,请选手自行编译使用。

本地校验器没有严格检查格式,请及时提交OJ以防意外爆零

将checker.cpp编译成checker后,在终端中运行

./checker <case_no>

其中case_no是测试数据的编号。例如

./checker 3

将测试C3.out是否可以接受同时在report.out里输出详细内容(windows用户请使用checker 3)。

直接在终端中运行./checker将测试所有数据是否可以接受。

运行./checker <input> <output>将测试以<input>作为输入<output>作为输出是否可以接受。

下载

输入数据及checker下载


或者逐个上传: