故事
AtCoder公司的高桥社长在办公室里玩着让小车跑来跑去的玩具。这个玩具会一直直行,直到碰到障碍物,碰到障碍物后会向右转90度,然后不断重复这个动作。不断重复这个动作的话,最终会以同样的方向经过已经经过的地方,之后会沿着相同的路线无限循环。
高桥社长虽然非常喜欢小车,但非常讨厌无限循环,所以他打算通过在办公室设置障碍物,制作一条可以在进入无限循环之前行驶尽可能长距离的路线。希望你能帮高桥社长一把。
(进入无限循环前的移动距离18)
問題文
n \times n 有一个格子棋盘。将最左上角的格子坐标记为 (0, 0) ,从那里向下 i 马格,向右方向 j 马格前进的目的格坐标 (i, j) 为。 青年状态下, (si, sj) 在该位置朝右方向放置有玩具车。
一些格子上以青少年状态设置了障碍物,这些障碍物不能被移除或移动到其他格子上。同时,n\times n 范围外的所有格子都视为放置了障碍物。剩余空白的格子可以自由设置障碍物。但保证玩具车的青少年状态位置不会设置障碍物,也不能在该位置新建障碍物。
当障碍物设置完成后,玩具车将按照以下规则移动。
- 当前方向前进一格的位置有障碍物时,玩具车将在该位置向右旋转90度。
- 如果在当前方向前进1格的前方没有障碍物,则向该方向前进1格。
如果不断重复这个动作,就会在某时用同一方向再次经过已经走过的格子,从那以后会无限循环相同路线。 请设置障碍物,使进入无限循环前的移动距离尽可能长。 这里的“进入无限循环前的移动距离”是指第一次到达以前相同位置且相同方向状态时,到此为止规则2的应用次数(如果最后是规则2,也包括在内)。
得点
确定进入无限循环之前行驶的距离。 L, 初始状态下空方格的总数为 当 E 时, 将获得以下分数。
\[\mathrm{round}\left(10^6\times\frac{L}{4 E}\right)\]
创建一个设置障碍的程序,以便您可以获得尽可能高的分数。
总共有100个测试用例,每个测试用例的总分就是提交分数。 测试用例中 第 i=1,2,\cdots,100 个输入是 n=20 + \mathrm{floor}(31 \times (i-1)/100) 满意。 如果一个或多个测试用例产生不正确的输出或超过时间限制,则整个提交将被评判。WA呀 它与TLE变为。 最终排名以比赛时间内获得的最高分决定,比赛结束后不再进行系统测试。如果多个参赛者得分相同,则无论提交时间如何,他们都会获得相同的排名。
入力
输入按以下形式从标准输入给出。
n
si sj
b_0
\vdots
b_{n-1}
n 代表板子的尺寸,
小于或等于20 以上 50 的整数值。
(si, sj) 代表玩具车的初始位置
小于或等于 0 以上 n-1 的整数值。
每个 b_i 是 # 和
将其放在 . 组成的长度为 n 及其 j (0\leq j\leq n-1) 第一个字符是坐标
如果 (i,j) 方块上放置了障碍物, #,如果未放置 . 。
出力
要安装的新障碍物总数 m 和要安装的障碍物的坐标为 (i_0,j_0),\cdots,(i_{m-1},j_{m-1}) ,按以下格式输出到标准输出。
m
i_0 j_0
\vdots
i_{m-1} j_{m-1}
同一个方格上不能放置多个障碍物,玩具车初始位置上不能放置任何障碍物。 如果不满足这些条件,WA 已确定。
入力生成方法
电路板尺寸 由 n 从 \mathrm{rand\_int}(20,50) 生成。 汽车的初始位置 由 si=\mathrm{rand\_int}(0,n-1)、sj=\mathrm{rand\_int}(0,n-1) 生成。
実数 p 从 \mathrm{rand\_double}(0.01,0.1) 并且除了汽车的初始位置之外,每个方格的概率是独立的 使用 p 放置障碍物。
工具(输入生成器/可视化器)
- 网页版:比本地版本性能更高,支持动画显示和手动播放。
- 本地版本:使用Rust 语言
请为准备编译环境。
- Windows 编译的二进制文件:如果您在构建 Rust 语言环境时遇到问题,请改用它。
入力例 1
20 10 8 .................... ........#........... .................... .................... .................... .....#.............# .................... ...................# .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ....................
出力例 1
31 19 19 18 7 2 9 16 0 17 18 19 9 0 12 16 11 13 0 14 18 16 17 15 12 11 13 12 18 13 17 8 0 9 7 11 6 10 1 6 2 9 18 3 1 0 5 6 4 5 2 2 3 3 17 6 16 5 12 3 19 2 14