#P18038. Cellular Component Constellation

Cellular Component Constellation

Cellular Component Constellation

题目描述

给定整数 N,MN,M,请将一个 N×NN\times N 的方格染成黑白两色,使:

  • 所有白色连通块的大小,恰好有 MM 种不同的值;
  • 所有黑色连通块的大小,恰好有 MM 种不同的值。

同色格子只能通过上下左右相邻的同色格子连通,不计对角线相邻。连通块是按这种关系连通的极大格子集合,大小为其中的格子数。

要求的是不同大小的种数,不是连通块个数。黑色与白色的大小集合可以不同,只要求两个集合的大小都为 MM。

如果存在多种方案,输出任意一种;如果不存在,输出无解。

输入格式

一行两个整数 N,MN,M。

2≤N≤20002\le N\le2000,1≤M≤20001\le M\le2000。

输出格式

有解时输出 NN 行,每行一个长度为 NN 的字符串。第 ii 行第 jj 个字符为 . 表示该格为白色,为 # 表示该格为黑色。

无解时仅输出一行 -1。

样例 1

输入:

4 2

输出:

###.
..##
##.#
.##.

样例 2

输入:

2 3

输出:

-1

样例 3

输入:

12 7

输出:

.#..#.#.##.#
.#.#..#.##.#
.##...#.##.#
.#.#..#.##.#
.#..#.##..##
......######
######......
#...##..###.
#.##.#.#....
#...##.#....
#.####.#....
#.####..###.

样例 1 中白色连通块大小集合为 {1,2}\{1,2\},黑色为 {4,6}\{4,6\},两个集合都恰有两种大小。