P7395 Marble Game (2021 CoE-I C)

$\operatorname{Alice}$ is getting a bit tired of the marble game. She often plays it on the computer. The reason she is tired is that she is already an expert at this game, and she can always draw with the computer. $\operatorname{Bob}$ created a new computer game for $\operatorname{Alice}$. The rules of this two-player computer game are as follows: (1) The game is played on the diamond-shaped board shown in the figure below.  (2) The two players take turns placing marbles. In one move, a player may place **from $1$ to $3$ marbles consecutively** on unoccupied positions in one of the following directions: horizontal, vertical, $45$-degree diagonal, or $135$-degree diagonal. If a player can place marbles, they must place at least $1$ marble. The following are examples of a legal single move (black dots indicate placed marbles, white dots indicate empty positions, and the board is empty before this move):  The following are examples of an illegal single move (black dots indicate placed marbles, white dots indicate empty positions, and the board is empty before this move):  Explanation of why they are illegal: ($a$) the three marbles are not on the same diagonal line (or vertical line); ($b$) there is one empty position between the two marbles; ($c$) the three marbles are not on the same diagonal line; ($d$) the three marbles are not on the same diagonal line (or vertical line); ($e$) $4$ marbles are placed at once; ($f$) the three marbles are not on the same horizontal line (or vertical line, or diagonal line). (3) If a player cannot place any more marbles, then that player loses and the other player wins. $\operatorname{Alice}$ always plays first, and she often plays this game with $\operatorname{Bob}$. After making some moves, $\operatorname{Bob}$ may leave and hand the game over to the computer agent, and the computer always places marbles using the optimal strategy. Given the game state after $\operatorname{Bob}$ leaves, your task is to determine whether $\operatorname{Alice}$ can possibly win against the computer.

**The input contains multiple sets of testdata**. The first line contains an integer $T$, the number of test cases. Then there is a blank line. Next come $T$ board states. Each board state consists of seven lines of characters, representing the game state after $\operatorname{Bob}$ leaves. `*` indicates that a marble has been placed on that position, and `.` indicates that the position is empty. There is a blank line between adjacent test cases.

For each test case, if $\operatorname{Alice}$ can win, output `Possible.`; otherwise output `Impossible.`.

#### Sample Explanation In the first test case, $\operatorname{Alice}$ can choose the remaining $3$ empty positions along the diagonal direction in the lower-left corner of the board and place $3$ marbles consecutively at once, so that the computer cannot place any more marbles afterwards. Therefore, $\operatorname{Alice}$ can win. In the second test case, $\operatorname{Alice}$ can choose the remaining $3$ empty positions along the fourth row and place $3$ marbles consecutively at once, so that the computer cannot place any more marbles afterwards. Therefore, $\operatorname{Alice}$ can win. In the third test case, there are two consecutive empty positions left in the second-to-last column. $\operatorname{Alice}$ can place $2$ marbles at once, so that the computer cannot place any marbles afterwards. Therefore, $\operatorname{Alice}$ will win. In the fourth test case, similar to the second test case, there are two consecutive empty positions left in the third row, so $\operatorname{Alice}$ will win. In the fifth test case, only two non-consecutive empty positions remain on the board. Since $\operatorname{Alice}$ can only choose one empty position and place $1$ marble in a single move, no matter what $\operatorname{Alice}$ does, the computer can always fill the remaining board with marbles in one move, making $\operatorname{Alice}$ unable to continue placing marbles. Therefore, $\operatorname{Alice}$ will lose. In the sixth test case, $\operatorname{Alice}$ can choose the middle two empty positions along the diagonal direction in the upper-right corner of the board and place $2$ marbles, turning the board state into the fifth test case of the sample input. Therefore, $\operatorname{Alice}$ will win. ------------ #### Constraints For $10\%$ of the data, $0 \lt T \leq 10$. For $60\%$ of the data, $0 \lt T \leq 10^3$. For $80\%$ of the data, $0 \lt T \leq 10^5$. For $100\%$ of the data, $0 \lt T \leq 10^6$. ------------ #### Hint The input size is large. Please use an appropriate input method. Translated by ChatGPT 5