490. Figure ans Spots
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard
Let's consider an infinite sheet of grid paper. Initially all the cells are white and you can paint some of them black.
Two cells are called 8-neigbours if they share a side or a corner. An 8-path between black cells
A and
B is a sequence of cells
X0 =
A,
X1, ·s,
XL-1,
XL =
B such that all cells in the sequence are black and for all 0 ≤
i <
L the cells
Xi and
Xi+1 are 8-neighbours. A set of black cells is called a figure if there is an 8-path from each of them into each other.
Two cells are called 4-neighbours if they share a side. A 4-path between white cells
A and
B is a sequence of cells
X0 =
A,
X1, ·s,
XL-1,
XL =
B such that all cells in the sequence are white and for all 0 ≤
i <
L the cells
Xi and
Xi+1 are 4-neigbours. A finite set of white cells is called a
if:
- There is a 4-path from each of them into each other.
- The previous condition is broken when any other white cell is added to the set.
We say that a figure has the height
H and the width
W if it fits in a rectangle
H rows high and
W columns wide, but does not fit in a rectangle
H-1 rows high and
W columns wide nor in a rectangle
H-1 rows high and
W columns wide.
The image above shows a figure with height 7 and width 9 and containing two spots.
Given the numbers
H,
W and
N, construct a figure with height exactly
H and width exactly
W and containing exactly
N spots.
Input
The input file contains several test cases. The first line of the file contains
T (1 ≤
T ≤ 100), the number of test cases. Each of the following
T lines describes one test case and contains three integers
H,
W and
N (1 ≤
H,
W ≤ 20, 1 ≤
N ≤ 200), separated by spaces.
Output
The output file should contain the following data for each test case:
- If it is possible to construct a figure with the given parameters, output any of the possible figures as H rows consisting of W characters each; output the character
.
for a black cell and the character #
for a white cell. - If it is impossible to construct the required figure, output a single line containing the word .
The output data for two different test cases should be separated by an empty line.
Example(s)
sample input | sample output |
3
7 9 2
20 20 22
5 5 10
|
#......##
#.#.....#
#.##.....
....####.
.#..##.#.
.#..##.#.
.#.......
.#####.######.#####.
..###...####...###..
...#.....##.....#...
....................
....##..##..#...#...
...#.#.#..#.##.##...
...###.#....#.#.#...
...#.#.#..#.#...#...
...#.#..##..#...#...
....................
....................
.###..##..###...##..
..#..#..#.#..#.#..#.
..#..#....###..#....
..#..#..#.#....#..#.
.###..##..#.....##..
....................
...#.....##.....#...
..###...####...###..
.#####.######.#####.
Impossible
|