Bacteria War

Problem

[ALPHANO] Bacterial War Rule Explanation (Youtube)

Two types of bacteria (O and X) compete for dominance on a $7 \times 7$ culture plate.

The culture plate consists of $1 \times 1$ cells arranged in $7$ rows and $7$ columns. Rows are numbered $1$ to $7$ from top to bottom, and columns are numbered $1$ to $7$ from left to right. A cell at the $x$-th row and $y$-th column is denoted as $(x, y)$.

Each cell can be in one of three states: empty ., first-player bacterium O, or second-player bacterium X. Initially, cells $(1, 1)$ and $(7, 7)$ contain the first-player bacterium O, while $(1, 7)$ and $(7, 1)$ contain the second-player bacterium X. The remaining 45 cells are empty ..

The battle begins with the first player O, and players O and X take turns. During their turn, a player can spread their bacteria by selecting a starting cell $(x_1, y_1)$ where their bacterium is located and an empty destination cell $(x_2, y_2)$.

• The movement distance $d = \max(|x_1 - x_2|, |y_1 - y_2|)$ must be either $1$ or $2$.
• If the movement distance is $1$, it is called Division. In a Division move, the bacterium at the starting cell $(x_1, y_1)$ remains, and a new bacterium of the same type is created at the destination cell $(x_2, y_2)$.
• If the movement distance is $2$, it is called a Leap. In a Leap move, the bacterium at the starting cell $(x_1, y_1)$ disappears (becoming an empty cell .), and a new bacterium is created at the destination cell $(x_2, y_2)$.
• Immediately after a Division or Leap action, Infection occurs. Infection means that any opponent's bacteria in the $8$ adjacent cells (horizontal, vertical, and diagonal) around the destination cell $(x_2, y_2)$ are converted to the current player's bacterium type.
• If there are no legal Division or Leap moves available, the player must select PASS. In this case, the turn passes without any change to the culture plate.

In summary, each player chooses either Division or Leap if a move is possible, followed by Infection. If no moves are possible, they must PASS.

Below is an example of the first player performing a Division from $(1, 1)$ to $(2, 2)$:

Below is an example of the second player performing a Leap from $(2, 2)$ to $(4, 4)$:

Finally, here is an example where the first player must select PASS:

The battle ends when any of the following conditions are met:

• One type of bacteria completely disappears from the board.
• There are no empty cells left on the board.
• Both players have performed $200$ actions each (total of $400$ turns).

At the end of the game, the player occupying more cells wins. If both players occupy the same number of cells, it is a draw.

Please design an AI to become the ultimate winner of the culture plate!

Input

The judge program communicates with the agent using single-line text commands as follows:

• x1, y1, x2, y2 are integers.
• my_time, opp_time, and time are integers representing time in milliseconds.
• After every output, you must print a newline character and flush the buffer.
• Failure to output within the time limit results in a Time Limit Exceeded (TLE) verdict.
• Outputting an invalid format or an illegal move during a TURN command results in a Runtime Error (RE) verdict.

Example

Sample Code

• C20: sample.c
• CPP20: sample.cpp
• PYTHON3, PYPY3: sample.py

Limit

• Time: For the first TURN command given to each agent, my_time is $10\,000$ ms.
• Memory: 1024MB
• Judging Environment: HELP > Judging Environment