故事
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格。但如果移动目标为墙壁或在棋盘外,移动将不进行。之后, P 该值应乘以 P+1 更新为。
-
发射墨水:指定上下左右方向,使用墨水发射器发射墨水。
墨水从你当前位置向指定方向最远 P 移动到格子上,并将通过的所有格子(包括你当前位置的格子)涂黑。不过,不能越过墙壁涂黑。
更严格来说, k = 0,1,2, \ldots, P 按照顺序执行以下处理。- 从你当前位置向指定方向 k 移动到的格子位置 (i,j) 。
- (i,j) 如果在棋盘外或是墙壁格子,则对于之后的 k 不进行处理并结束。
- (i,j) 如果该格子仍未被涂黑,则涂黑。
之后, P 该值应乘以 \lfloor P/2 \rfloor + 1 更新为。
-
帕斯: 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) 。
- 当选定的方格被制作成墙方格时,棋盘上的所有地板方格不再相连。
工具(输入生成器/可视化工具)
- 网页版:比本地版本性能更高,支持动画显示和手动播放。
- 本地版本:使用Rust 语言
请为准备编译环境。
- Windows 编译的二进制文件:如果您在构建 Rust 语言环境时遇到问题,请改用它。
竞赛期间,禁止分享可视化结果或提及解决方案或注意事项。请小心。
入力例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