P3858 [TJOI2008] Snake

Jiajia and Jinming are playing a new competitive version of the Snake game in a rectangular prism. Some cells are obstacles, and every other cell initially contains food. Jiajia places the snake on a cell that has food. Then Jinming moves the snake one step to an adjacent cell that has food; then Jiajia moves it one step; they alternate in this way. A move may go only in one of the six directions: up, down, left, right, front, or back. The snake cannot leave the rectangular prism or enter an obstacle cell. Moreover, every move must eat new food: the snake may not revisit any previously visited cell, including the starting cell. When a player can no longer move the snake under these rules, that player loses.

Jiajia and Jinming are very smart and always play optimally. Since the snake’s starting position is chosen by Jiajia, she wants to know whether she can pick a starting cell that guarantees her a win.

The first line contains an integer N, the number of test cases. Each test case begins with a line containing three integers H, R, and C, denoting the height, length, and width of the rectangular prism. Then follow H matrices of R rows and C columns; each matrix describes one layer of the prism. Each matrix contains only the characters '.' and 'X', where '.' means a cell initially with food and 'X' means an obstacle. The H layer descriptions are separated by a blank line.

Output N lines, each indicating whether Jiajia can guarantee a win in the corresponding game. Output "yes" if she can, otherwise output "no".

- For 40% of the testdata, $H \times R \times C \le 16$. - For 100% of the testdata, $H \times R \times C \le 100$, $N \le 10$. - The input guarantees that each rectangular prism contains at least one cell that is not an obstacle. Translated by ChatGPT 5