← 返回题目列表

AtCoder · atcoder13live_a

A. 粉刷地板

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

故事

AtCoder公司的高桥社长为了办公室的重新布置,想要重新涂刷所有地板的颜色。然而,办公室很大,要重新涂刷所有地板需要时间。

于是高桥社长开发了一种装置,叫做“喷墨机”。喷墨机会随着时间的流逝积累能量,通过消耗当前一半的能量,可以根据能量的大小一次性沿直线涂刷一定距离的地板。

希望利用喷墨机,考虑一种高效覆盖涂刷所有地板的方法。

問題文

N \times N 有一个棋盘。左上角的格子记为 (0,0) ,向下方向数 i 格,向右方向数 j 格的位置的格子记为 (i,j) 。 N \times N 。棋盘的外部全部被墙壁覆盖,无法通行。棋盘上有地板格和墙壁格, N \times N 在格子中, M 一个是墙格。 保证所有的地板格都是连通的。

你在少年工厂。 (s_i, s_j) 此外,你拥有一台名为“喷墨装置”的设备。喷墨装置有一个力量值 P 在青少年状态下 P=0 。

你可以在以下三种行动中选择一种最多 T 可以进行回合操作。

  1. 移動:指定上下左右方向移动1格。但如果移动目标为墙壁或在棋盘外,移动将不进行。之后, P 该值应乘以 P+1 更新为。

  2. 发射墨水:指定上下左右方向,使用墨水发射器发射墨水。
    墨水从你当前位置向指定方向最远 P 移动到格子上,并将通过的所有格子(包括你当前位置的格子)涂黑。不过,不能越过墙壁涂黑。
    更严格来说, k = 0,1,2, \ldots, P 按照顺序执行以下处理。

    • 从你当前位置向指定方向 k 移动到的格子位置 (i,j) 。
    • (i,j) 如果在棋盘外或是墙壁格子,则对于之后的 k 不进行处理并结束。
    • (i,j) 如果该格子仍未被涂黑,则涂黑。

    之后, P 该值应乘以 \lfloor P/2 \rfloor + 1 更新为。

  3. 帕斯: P 该值应乘以 P+1 更新为。

为了尽可能多地涂黑格子,并且如果可以将所有格子涂黑则尽可能快地涂黑,决定行动。

得点

所有行动结束后未能涂黑的格子数为 X ,行动次数为 K 情况下,可以获得以下得分。

  • X > 0 的情况下,N^2 - X
  • X = 0 的情况下,N^2 + T - K

得分越高越好。

总共有 100 个测试用例,每个测试用例的得分总和即为提交的得分。如果一个或多个测试用例出现非法输出或超出限制的情况,则提交全部的原则将WA或TLE变为。


入力

棋盘的大小 N 、墙的数量 M 、最大行動回数 T 、初期位置 (s_i, s_j) 、棋盘的信息 S 将以以下格式从标准输入提供。

N M T s_i s_j
S_{0,0}S_{0,1}S_{0,2}\cdotsS_{0,N-1}
S_{1,0}S_{1,1}S_{1,2}\cdotsS_{1,N-1}
\vdots
S_{N-1,0}S_{N-1,1}S_{N-1,2}\cdotsS_{N-1,N-1}
  • N = 20
  • 0 \leq M \leq 30
  • T = 250
  • 0 \leq s_i, s_j < N
  • S_{i,j} 的 . 情况下 (i,j) 是地板格,# 情况下 (i,j) 是一个墙方块。
  • 初期位置 (s_i, s_j) 是地板质量。
  • 板上的所有地板空间均已连接。

出力

操作数 K ,按以下格式输出到标准输出。

K
op_1
op_2
\vdots
op_K

行動回数 K 是 必须满足 K \leq T 。 op_i 是 i 表示第一个动作,并根据动作类型以以下格式输出。

移動:

1 d

这里 d 是一个表示移动方向的字符,上图:U、下:D、左:L、右:R 。

发射墨水:

2 d

这里 d 是表示墨水喷射方向的字符,上图:U、下:D、左:L、右:R 。

帕斯:

3

参见示例 从板上随机选择

入力生成方法

  • 初期位置 (s_i, s_j) 。
  • 墙方格数 M 该值应乘以 0 以上 30 从以下整数中随机选择。 使用地面质量初始化所有
  • 盤面 S 。
  • 盤面 S 墙面空间为 重复将随机方块变成墙方块的操作,直到获得 M 。但是,如果满足以下任一条件,请重新选择该方块,而不执行任何操作。
    • 所选方格已经是墙方格。
    • 所选方格为初始位置 (s_i, s_j) 。
    • 当选定的方格被制作成墙方格时,棋盘上的所有地板方格不再相连。

工具(输入生成器/可视化工具)

竞赛期间,禁止分享可视化结果或提及解决方案或注意事项。请小心。


入力例1

20 15 250 0 0
....................
........#...........
..........#.........
....................
....................
.#..................
..................#.
....................
....................
....................
..#...##............
................#...
....................
.....#.........#....
...........#........
....................
.............#....#.
..#.............#...
....................
....................

出力例1

9
1 R
2 R
1 D
2 D
1 L
2 L
1 U
2 U
3