N Cellular Component Constellation
問題\(2\) つの整数 \(N,\ M\) が与えられます。
各マスが白または黒に塗られた \(N \times N\) グリッドであって以下の条件を満たすものを、出力の項で指定されたフォーマットに従って一つ出力してください。条件を満たすものが存在しない場合は -1 を出力してください。
- グリッドに含まれる白く塗られたマスの連結成分の大きさはちょうど \(M\) 種類
- グリッドに含まれる黒く塗られたマスの連結成分の大きさはちょうど \(M\) 種類
解が複数ある場合、どれを出力しても構いません。
\(1\) 行目に整数 \(N,M\) がこの順に空白区切りで与えられる。 ( \(2 \leq N \leq 2000, 1 \leq M \leq 2000\) )
部分点: \(2M \leq N \leq 100\) を満たすデータセットに正解した場合 \(1\) 点が与えられる。
条件を満たすグリッドが存在する場合、\(N\) 行出力せよ。このうちの \(i\) 行目 \((1 \leq i \leq N)\) には以下のような長さ \(N\) の文字列 \(s_i\) を出力せよ。
- 構成したグリッドの \(i\) 行 \(j\) \((1 \leq j \leq N)\) 列のマスが白く塗られているならば、\(s_i\) の \(j\) 文字目は . である。
- 構成したグリッドの \(i\) 行 \(j\) \((1 \leq j \leq N)\) 列のマスが黒く塗られているならば、\(s_i\) の \(j\) 文字目は # である。
条件を満たすグリッドが存在しない場合、\(1\) 行目に -1 を出力せよ。
4 2
###. ..## ##.# .##.
2 3
-1
12 7
.#..#.#.##.# .#.#..#.##.# .##...#.##.# .#.#..#.##.# .#..#.##..## ......###### ######...... #...##..###. #.##.#.#.... #...##.#.... #.####.#.... #.####..###.
\(2\) つの白く塗られたマス \(c_1,\ c_2\) が連結であるとは、マス \(c_1\) からマス \(c_2\) へ、上下左右に隣り合うマスへの移動を繰り返して、白く塗られたマスだけを通って移動できることを意味します。
白く塗られたマスの集合 \(S\) が連結成分であるとは、\(S\) が以下の条件を満たすことを意味します。
- \(S\) のどの \(2\) つのマスも連結である。
- \(S\) に含まれないどの白く塗られたマスと、\(S\) に含まれるどのマスも連結ではない。
黒く塗られたマスについても連結成分を同様に定義します。
各連結成分について、含まれるマスの数を連結成分の大きさとします。
以下、付録
サンプル出力 \(1\) の説明
白く塗られたマスの連結成分の大きさは \(1\) と \(2\) の \(2\) 種類です。 黒く塗られたマスの連結成分の大きさも \(4\) と \(6\) の \(2\) 種類です。
サンプル出力 \(1\) の図
サンプル出力 \(3\) の図
