ACPC 2020 - Division 1

Start

2020-11-14 10:00 AKST

ACPC 2020 - Division 1

End

2020-11-14 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -10 days 19:24:48

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
Monochromatic Minesweeper

/problems/acpc20.monochromaticminesweeper/file/statement/en/img-0001.png
A possible solution for Sample Input $2$. Every cell with a $3$ is adjacent to exactly $3$ bombs, and in total there are $16$ bombs. No $6$ by $6$ $3$-uniform board with $15$ bombs or less exists.

In the game of minesweeper you are given a rectangular grid of a particular size. At the beginning of the game, the contents of all cells are hidden. The player can reveal the content of a cell by clicking on it. Some cells contain mines, and all other cells contain a number between $0$ and $8$ indicating the number of mines in the $8$ neighbouring cells (vertically, horizontally, and diagonally). Cells outside the boundary of the grid are assumed not to contain mines. The objective of the game is to reveal all of the cells containing numbers, without revealing any mines. A careful player can often win by using the revealed numbers to deduce exactly which cells contain mines, while only having to guess a few times over the course of the game.

Minesweeper can be a dangerously addictive game, so you have been assigned to a task force intended to eliminate minesweeper addiction once and for all. Your job is to construct minesweeper boards that are so frustrating to play that any player who tries to solve one will immediately give up on the game forever.

In particular, you will need to find boards with a certain structure which we will now describe. We call a board $k$-uniform if every cell contains either a mine or a specific number $k$. For some $k$, all you need to do is find any $k$-uniform board of the given height $h$ and width $w$ with the smallest possible number of mines.

Input

The input will contain a single line with $3$ integers $w$, $h$, and $k$, where $1\le w\le 50$, $1\le h\le 8$, and $0\le k\le 8$.

Output

The first line of output must contain the smallest possible number of mines in any $k$-uniform $h$ by $w$ board. The next $h$ lines must contain $w$ characters specifying any such board. The hash character # indicates a mine, and the period character . indicates that no mine is present.

Sample Input 1 Sample Output 1
3 3 1
1
...
.#.
...
Sample Input 2 Sample Output 2
6 6 3
16
#.#..#
.#.##.
#...#.
.#...#
.##.#.
#..#.#