Problem G
Diamonds

Diamond, Minecraft Wiki

As a child, Steve yearned for the mines.

Now it is his task to mine diamonds for the group. Steve has identified a rectangular volume that he plans to mine in search of diamonds. Steve knows that diamonds always form in 2x2x2 cubes (simplified for the sake of this problem), and he wants to find them as quickly as possible.

To do this, Steve has decided to dig parallel tunnels through the volume, knowing that he will be able to find any diamonds that he passes by. Specifically, Steve will find a diamond vein if he mines through it or adjacent to it. With his experience, Steve will also know if he is diagonal to a diamond block! As much as he loves the mines, he hates crawling through them, so he plans to make all tunnels at least two blocks tall so that he can stand upright in them.

To reduce the time needed, Steve wants to minimize the number of blocks mined while still ensuring that he finds all of the diamonds. Can you help him identify an optimal strategy?

Sample 1 Solution, Minecraft 1.21.5

Input

The input is a single line with two integers, $r$ and $c$, corresponding to the number of rows and columns in the area that Steve is going to mine.

You are given that $2 \le r, c \le 100$.

Output

Output a 2d grid of $r$ rows and $c$ columns consisting of either ’.’ or ’X’, where X indicates the locations of the tunnels that Steve should dig.

Your output should meet the following constraints.

• All tunnels are at least two blocks tall - each ’X’ has another ’X’ above or below it.

• The set of tunnels is adjacent (including diagonals) to all possible diamond vein locations (or through them).

• The total number of ’X’ is minimized.

When there are multiple such solutions, you may output any of them.

5 8

........
.X......
.X...X..
.....X..
........

2 5

..X..
..X..

7 4

....
....
..X.
..X.
..X.
....
....