← 返回题目列表

AtCoder · ahc010_a

A. 循环线

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

故事

喜欢循环线的高桥正在玩玩具火车。 如下图所示,该玩具由包含铁路线的方形瓷砖组成。 通过旋转瓷砖,他可以连接线路并玩在线路上运行的玩具火车。 由于高桥有两列玩具火车,因此请尽可能创建两条大环线。

初始状态。 旋转右上角的图块和右中的图块后。

问题陈述

您将获得包含排列在 30 x 30 正方形中的铁路线的图块。 根据旋转方向的不同,瓷砖有 8 种类型,编号如下。

0 1 2 3 4 5 6 7

图块 0 到 3 包含一条曲线,图块 4 和 5 包含两条曲线,图块 6 和 7 包含一条直线。 每块瓷砖可以每 90 度旋转一次。 将图块逆时针旋转 90 度,图块将变成如下所示。

1 2 3 0 5 4 7 6

由于线路上没有分支,因此每条线路都是路径或循环的一部分。 形成一个循环的一组线称为“循环线”,其长度定义为沿着循环线的往返行程中从一个图块移动到其相邻图块的次数。 例如,下面的循环线由 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).

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

在比赛结束之前不允许共享可视化结果。


示例输入 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