A - Loop Lines Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

ストーリー

環状線が大好きな高橋くんは鉄道玩具で遊んでいる。 この玩具は、下図のように並べられた正方形の線路タイルを回転させることで線路を繋ぎ、その上を電車の模型を走らせるというものである。 高橋くんは電車の模型を2台持っているので、出来るだけ大きな環状線を2つ作ってほしい。

初期状態 右上と右中央を回転

問題文

30\times 30 マスに並んだ線路タイルが与えられる。 タイルは回転したものを区別すると8種類あり、以下のように番号付ける。

0 1 2 3 4 5 6 7

0から3番のタイルにはカーブした1本の線路、4番と5番のタイルにはカーブした2本の線路、6番と7番のタイルには直線の1本の線路が乗っている。 各タイルは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 個あり、各テストケースの得点の合計が提出の得点となる。 1つ以上のテストケースで AC 以外の判定がされた場合、提出の得点は0点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、その得点を獲得した提出の早い方が上位となる。

環状線の長さの求め方のヒント

疑似コードを更新しました。 環状線の長さは例えば以下のようにして計算できる。 タイルの状態が入った二次元配列を 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]; // 次のタイルの方向
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; // 今居たタイルの方向

あとはこの処理を最初の位置と向き(同じタイルを二度通る可能性があることに注意)に戻ってくるまで繰り返せば、繰り返し回数が環状線の長さとなる。

// (si, sj) のタイルに sd 方向のタイルから侵入した状態からスタートして環状線の長さを求める
i = si;
j = sj;
d = sd;
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 (0\leq i\leq 29) 番目、左から j (0\leq j\leq 29) 番目のタイルを (i, j) と表す。 t_{i,j} はタイル (i,j) の状態を表す 0 以上 7 以下の数字である。

出力

タイル (i,j) を反時計回りに90度回転させる回数を r_{i,j} (0\leq r_{i,j}\leq 3) としたとき、30i+j 文字目が r_{i,j} となるような長さ 900 の文字列を1行に出力せよ。

解を複数回出力しても良い。複数出力された場合は一番最後のもののみが採点に用いられる。ビジュアライザでは複数出力された解の比較が可能である。

例を見る

入力生成方法

L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(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

Story

Takahashi, who loves loop lines, is playing with a toy train. As shown in the figure below, this toy consists of square tiles containing railroad lines. By rotating the tiles, he can connect lines and play with toy trains running on the lines. Because Takahashi has two toy trains, please create two large loop lines as much as possible.

Initial State. After rotating the top-right tile and the middle-right tile.

Problem Statement

You are given tiles containing railroad lines arranged in a 30 x 30 square. There are 8 types of tiles by distinguishing rotations which are numbered as follows.

0 1 2 3 4 5 6 7

Tiles 0 to 3 contain one curved line, tiles 4 and 5 contain two curved lines, and tiles 6 and 7 contain one straight line. Each tile can be rotated every 90 degrees. By rotating a tile 90 degrees counterclockwise, the tile will become as follows.

1 2 3 0 5 4 7 6

Since there are no branches on the lines, each line is part of a path or cycle. A set of lines forming a cycle is called a "loop line," and its length is defined as the number of times to move from a tile to its adjacent tile in a round trip along the loop line. For example, the loop line below consists of 7 tiles, but its length is 8 because it passes through the center tile twice.

Your task is to determine the number of times to rotate each tile.

Scoring

Let L_1 be the length of the longest loop line obtained by rotating the tiles according to the output, and L_2 be the length of the second longest one (L_1=L_2 if there is more than one longest one). Then, you will get a score of L_1\times L_2. If the number of loop lines is less than or equal to 1, the score for that test case is 0.

There are 100 test cases, and the score of a submission is the total score for each test case. If you get a result other than AC for one or more test cases, the score of the submission will be zero. The highest score obtained during the contest time will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, the ranking will be determined by the submission time of the submission that received that score.

Hints on how to compute the length of a loop line.

Pseudo code has been updated. You can compute the length of a loop line, for example, as follows. Let tiles be a two-dimensional array containing the tile states. By numbering the directions 0, 1, 2, 3 in order of left, up, right, and down, the change in coordinates is represented by the arrays di = [0, -1, 0, 1] and dj = [-1, 0, 1, 0]. When a train enters a tile of state t from its adjacent tile in direction d, let to[t][d] be the direction to the next tile, or -1 if the train cannot enter from such a direction, then we obtain the following two-dimensional array.

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],
];

When a train enters tile at position (i, j) from its adjacent tile in direction d, you can update these variables as follows.

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.

After repeating this process until the train returns to its initial position and direction (note that it may pass through the same tile twice), the number of iterations is the length of the loop line.

// 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;
}

Input

Input is given from Standard Input in the following format:

t_{0,0} \cdots t_{0,29}
\vdots
t_{29,0} \cdots t_{29,29}

Each t_{i,0}\cdots t_{i,29} is a string of 30 characters. Let (i,j) denote the i-th (0\leq i\leq 29) tile from the top and j-th (0\leq j\leq 29) tile from the left. Then, t_{i,j} is an integer between 0 and 7 representing the state of the tile (i, j).

Output

Let r_{i,j} (0\leq r_{i,j}\leq 3) be the number of times the tile (i,j) is rotated 90 degrees counterclockwise. Output a string of length 900 such that the 30i+j-th character is r_{i,j} in one line to Standard Output.

Show example

Input Generation

Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive.

Each t_{i,j} is independently generated as follows.

  • With probability 25%, t_{i,j}=\mathrm{rand}(0, 3).
  • With probability 50%, t_{i,j}=\mathrm{rand}(4, 5).
  • With probability 25%, t_{i,j}=\mathrm{rand}(6, 7).

Tools (Input generator and visualizer)

Sharing visualization results is not allowed until the end of the contest.

Sample Input 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

Sample Output 1

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000