Oni Board Shift

Ported from Frontier-CS algorithmic/problems/169.

Agentics Interface

Each run executes the submitted zip_project solution once. The run command receives the case input on standard input and must write the candidate answer to standard output. The solution must not use the network during setup, build, or run.

The trusted separated evaluator compiles and runs the source-derived Frontier-CS checker against stdout.txt. Public validation contains one tiny deterministic case. Official cases, reference answers, and scoring metadata are supplied only through the required private asset official-runs.

Scoring

The primary metric is score, the average normalized Frontier-CS checker score on a 0-100 scale. Outputs rejected by the checker receive zero for that case. Official result details are score-only; public validation includes per-case feedback from the checker.

Original Statement

Story

Today, on February 2nd, the traditional Japanese event Setsubun is being celebrated in Japan. Setsubun is a ritual to ward off evil spirits and invite good fortune at the turning of the seasons. People chant "Oni wa soto!" ("Demons out!") while throwing roasted soybeans to drive away evil spirits (oni) and chant "Fuku wa uchi!" ("Fortune gods in!") to welcome Fukunokami, the deities of good fortune.

Takahashi is playing a board game called "Oni wa Soto, Fuku wa Uchi", inspired by the Setsubun tradition. The objective of this game is also to drive away demons and invite Fukunokami.

Find a sequence of moves that maximizes the score.

Problem Statement

There is an $N\times N$ square board. Let $(0, 0)$ be the coordinates of the top-left square, and $(i, j)$ be the coordinates of the square located $i$ squares down and $j$ squares to the right from there. The set of squares $(i,0), (i,1), \dots, (i,N-1)$ is referred to as row $i$, and the set of squares $(0,j), (1,j), \dots, (N-1,j)$ is referred to as column $j$.

Initially, there are Oni (demons) <img src="./images/oni.png" width="25"> and Fukunokami (fortune gods) <img src="./images/fuku.png" width="25"> pieces on the board, with $2N$ pieces of each type, all placed on distinct squares.

You can select one row or column in a single operation and shift the chosen row/column by one square in either the left/right or up/down direction.

• Shifting row $i$ to the left: The piece on square $(i,0)$ is removed from the board, and for each $j=1, \dots, N-1$, the piece on square $(i,j)$ moves to $(i,j-1)$.
• Shifting row $i$ to the right: The piece on square $(i,N-1)$ is removed from the board, and for each $j=0, \dots, N-2$, the piece on square $(i,j)$ moves to $(i,j+1)$.
• Shifting column $j$ upward: The piece on square $(0,j)$ is removed from the board, and for each $i=1, \dots, N-1$, the piece on square $(i,j)$ moves to $(i-1,j)$.
• Shifting column $j$ downward: The piece on square $(N-1,j)$ is removed from the board, and for each $i=0, \dots, N-2$, the piece on square $(i,j)$ moves to $(i+1,j)$.

You can perform up to $4N^2$ operations.

Your goal is to remove all the Oni from the board using as few moves as possible, without removing any Fukunokami.

Scoring

Let $T$ be the number of operations in the output sequence, $X$ be the number of Oni remaining on the board, and $Y$ be the number of Fukunokami removed from the board. Then, you will obtain the following score.

• If $X=0$ and $Y=0$, the score is $8N^2 - T$.
• If $X>0$ or $Y>0$, the score is $4N^2 - N (X+Y)$.

There are $150$ test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Wrong Answer">WA</span> or <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Time Limit Exceeded">TLE</span> , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.

Input

Input is given from Standard Input in the following format:

$N$
$C_0$
$\vdots$
$C_{N-1}$

• The board size $N$ is fixed at $N=20$ for all test cases.
• For each $i=0,1,\dots,N-1$, $C_i$ represents the initial state of row $i$ as a string of length $N$, where the $j$-th character is one of the following:
  • x: An Oni is present.
  • o: A Fukunokami is present.
  • .: Neither an Oni nor a Fukunokami is present.
• There are exactly $2N$ Oni and $2N$ Fukunokami on the board.
• For every square initially occupied by an Oni, at least one of the following conditions is guaranteed to hold. This ensures that there always exists a sequence of at most $4N^2$ moves that removes all Oni while keeping all Fukunokami on the board.
  • All squares above it in the same column do not contain a Fukunokami.
  • All squares below it in the same column do not contain a Fukunokami.
  • All squares to the left of it in the same row do not contain a Fukunokami.
  • All squares to the right of it in the same row do not contain a Fukunokami.

Hint

For a square $(i,j)$ occupied by an Oni, if there is no Fukunokami in the upward direction, performing an upward shift $i+1$ times followed by a downward shift $i+1$ times will remove the Oni at $(i,j)$ without removing any Fukunokami. Similarly, if there are no Fukunokami in the downward, leftward, or rightward directions, the Oni can be removed using the corresponding sequence of moves.

Since this operation does not change the positions of the remaining pieces on the board, applying it to all Oni ensures that all Oni are removed without removing any Fukunokami.

Output

Each operation at step $t$ is represented as a pair $(d_t, p_t)$, where $d_t$ is a character indicating the direction and $p_t$ is an integer indicating the row or column index.

• Shifting row $i$ to the left: (L, $i$)
• Shifting row $i$ to the right: (R, $i$)
• Shifting column $j$ upward: (U, $j$)
• Shifting column $j$ downward: (D, $j$)

Then, output to Standard Output in the following format:

$d_0$ $p_0$
$\vdots$
$d_{T-1}$ $p_{T-1}$

The number of operations $T$ must not exceed $4N^2$. If the limit is exceeded, the output will be judged as <span class='label label-warning' data-toggle='tooltip' data-placement='top' title="Wrong Answer">WA</span>.

<a href="https://img.atcoder.jp/ahc042/cnhLtdRT.html?lang=en&seed=0&output=sample">Show example</a>

Input Generation

First, $2N$ distinct squares are randomly selected from the $N^2$ squares on the board to determine the positions of the $2N$ Fukunokami pieces.

Next, all squares satisfying at least one of the following conditions are listed, forming the set $S$:

• All squares above it in the same column do not contain a Fukunokami.
• All squares below it in the same column do not contain a Fukunokami.
• All squares to the left of it in the same row do not contain a Fukunokami.
• All squares to the right of it in the same row do not contain a Fukunokami.

If the number of elements in $S$ is less than $2N$, the Fukunokami placement process is repeated.

Finally, $2N$ squares are randomly selected from $S$ to determine the positions of the $2N$ Oni pieces.

Tools (Input generator and visualizer)

• <a href="https://img.atcoder.jp/ahc042/cnhLtdRT.html?lang=en">Web version</a>: This is more powerful than the local version providing animations and manual play.
• <a href="https://img.atcoder.jp/ahc042/cnhLtdRT.zip">Local version</a>: You need a compilation environment of <a href="https://www.rust-lang.org/">Rust language</a>.
  • <a href="https://img.atcoder.jp/ahc042/cnhLtdRT_windows.zip">Pre-compiled binary for Windows</a>: If you are not familiar with the Rust language environment, please use this instead.

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.