故事
喜欢循环线的高桥正在玩玩具火车。 如下图所示,该玩具由包含铁路线的方形瓷砖组成。 通过旋转瓷砖,他可以连接线路并玩在线路上运行的玩具火车。 由于高桥有两列玩具火车,因此请尽可能创建两条大环线。
| 初始状态。 | 旋转右上角的图块和右中的图块后。 |
问题陈述
您将获得包含排列在 30 x 30 正方形中的铁路线的图块。 根据旋转方向的不同,瓷砖有 8 种类型,编号如下。
图块 0 到 3 包含一条曲线,图块 4 和 5 包含两条曲线,图块 6 和 7 包含一条直线。 每块瓷砖可以每 90 度旋转一次。 将图块逆时针旋转 90 度,图块将变成如下所示。
由于线路上没有分支,因此每条线路都是路径或循环的一部分。 形成一个循环的一组线称为“循环线”,其长度定义为沿着循环线的往返行程中从一个图块移动到其相邻图块的次数。 例如,下面的循环线由 7 个图块组成,但其长度为 8,因为它两次穿过中心图块。
您的任务是确定每个图块的旋转次数。
评分
让 L_1 是根据输出旋转图块获得的最长循环线的长度,并且 L_2 是第二长的长度(L_1=L_2 如果有多个最长的)。 然后,你将获得分数 L_1\times L_2。 如果循环线数小于或等于 1,该测试用例的分数是 0.
有100个测试用例,提交的分数是每个测试用例的总分。如果您得到的结果不是 AC 对于一个或多个测试用例,提交的分数将为零。比赛时间内获得的最高分将决定最终排名,比赛结束后不进行系统测试。如果超过一名参赛者获得相同分数,则排名将根据获得该分数的提交作品的提交时间来确定。
有关如何计算循环线长度的提示。
tiles 是包含图块状态的二维数组。
通过将方向0、1、2、3按照左、上、右、下的顺序编号,用数组来表示坐标的变化 di = [0, -1, 0, 1] 和 dj = [-1, 0, 1, 0]。
当火车进入某个州时 t 从其相邻图块的方向 d,让 to[t][d] 是到下一个图块的方向,或者 -1 如果火车无法从这个方向进入,那么我们得到如下二维数组。
to = [
[1, 0, -1, -1],
[3, -1, -1, 0],
[-1, -1, 3, 2],
[-1, 2, 1, -1],
[1, 0, 3, 2],
[3, 2, 1, 0],
[2, -1, 0, -1],
[-1, 3, -1, 1],
];
当火车进入该位置的方块时 (i, j) 从其相邻图块的方向 d,您可以按如下方式更新这些变量。
d2 = to[tiles[i][j]][d]; // Direction to the next tile if (d2 == -1) return 0; // The line is broken. i += di[d2]; j += dj[d2]; if (i < 0 || i >= 30 || j < 0 || j >= 30) return 0; // The line is broken. d = (d2 + 2) % 4; // Direction to the previous tile.
重复这个过程直到火车返回到其初始位置和方向(注意它可能会经过同一个图块两次),迭代次数就是循环线的长度。
// Suppose that a train enters a tile (si, sj) from direction sd.
i = si;
j = sj;
d = sd;
length = 0;
loop {
d2 = to[tiles[i][j]][d];
if (d2 == -1) return 0;
i += di[d2];
j += dj[d2];
if (i < 0 || i >= 30 || j < 0 || j >= 30) return 0;
d = (d2 + 2) % 4;
length += 1;
if (i == si && j == sj && d == sd) return length;
}
输入
输入由标准输入按以下格式给出:
t_{0,0} \cdots t_{0,29}
\vdots
t_{29,0} \cdots t_{29,29}
每个 t_{i,0}\cdots t_{i,29} 是一串 30 字符。 让 (i,j) 表示 i-th (0\leq i\leq 29) 从顶部平铺并 j-th (0\leq j\leq 29) 从左侧开始平铺。 然后, t_{i,j} 是介于 0 和 7 代表图块的状态 (i, j).
输出
让 r_{i,j} (0\leq r_{i,j}\leq 3) 是平铺的次数 (i,j) 逆时针旋转 90 度。 输出一个长度的字符串 900 这样 30i+j- 第一个字符是 r_{i,j} 在一行中连接到标准输出。
输入生成
让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。
每个 t_{i,j} 独立生成如下。
- 概率为 25%, t_{i,j}=\mathrm{rand}(0, 3).
- 概率为 50%, t_{i,j}=\mathrm{rand}(4, 5).
- 概率为 25%, t_{i,j}=\mathrm{rand}(6, 7).
工具(输入生成器和可视化工具)
- 网页版:这个比本地版本更强大,可以显示动画。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
在比赛结束之前不允许共享可视化结果。
示例输入 1
436204751575440756541724746755 347475575404531645424640344414 556644445442451553264555436757 761235545455474254546631467555 356447405421445153457656535564 014274425356522445253477726464 311765446655556346633757446600 471744514426443445162555525455 616053450444473274742055767455 254124557527462423444450075637 046546764557475436717475255501 752005462554554414031525515356 452524742177476245065554577605 664465643742341605007655253777 444571276444165545442447340356 435050335454565235025507452540 467560030465475447567644441426 735730577745561712541450443547 472675153755474445700540444544 507472724556677621365747544757 535177720776402476665547676174 636275455643650141456764547131 164624553536572554544165746536 521574724335644274433544442556 576732703453654464555315065544 656244747015464523316444145414 555646775254464367454454067475 665624154657072514445150474444 570004746554540445465051654541 635504417414262014475547424275
示例输出 1
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000