atcoder#ARC093B. [ABC092D] Grid Components
[ABC092D] Grid Components
配点 : 点
問題文
つの整数 が与えられます。
各マスが白または黒に塗られたグリッドであって以下の条件を満たすものを、出力の項で指定されたフォーマットに従って一つ出力してください。
- グリッドの大きさを縦 行横 列としたとき、 および はともに 以下である。
- 白く塗られたマスの集合はちょうど 個の連結成分に分かれている (連結成分という単語の定義については後の注釈を参照)。
- 黒く塗られたマスの集合はちょうど 個の連結成分に分かれている。
制約の項で指定される条件のもとで解は必ず一つ以上存在することが証明できます。 解が複数ある場合、どれを出力しても構いません。
注釈
つの白く塗られたマス が連結であるとは、マス からマス へ、上下左右に隣り合うマスへの移動を繰り返して、 白く塗られたマスだけを通って移動できることを意味します。
白く塗られたマスの集合 が連結成分であるとは、 が以下の条件を満たすことを意味します。
- のどの つのマスも連結である。
- に含まれないどの白く塗られたマスと、 に含まれるどのマスも連結ではない。
黒く塗られたマスについても連結成分を同様に定義します。
制約
入力
入力は以下の形式で標準入力から与えられる。
出力
以下の形式で出力せよ。
- 行目には構成したグリッドの大きさを表す整数 を空白を区切りとして出力せよ。
- 続いて 行出力せよ。このうちの 行目 () には以下のような長さ の文字列 を出力せよ。- 構成したグリッドの 行 () 列のマスが白く塗られているならば、 の 文字目は
.
である。- 構成したグリッドの 行 () 列のマスが黒く塗られているならば、 の 文字目は
#
である。
- 構成したグリッドの 行 () 列のマスが黒く塗られているならば、 の 文字目は
2 3
3 3
##.
..#
#.#
この出力は以下のグリッドに対応します。
7 8
3 5
#.#.#
.#.#.
#.#.#
1 1
4 2
..
#.
##
##
3 14
8 18
..................
..................
....##.......####.
....#.#.....#.....
...#...#....#.....
..#.###.#...#.....
.#.......#..#.....
#.........#..####.