acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem G

三密回避

ICPC 社の社員であるあなたは,新しいオフィスでの座席の配置の計画を任された. あなたの仕事は,三密回避のための条件を守りつつ室内になるべく多くの座席を配置することである. そこで,あなたはグリッドを用いたシミュレーションで問題を解くことにした.

シミュレーションでは部屋を長方形のグリッドで表す. グリッドの各マスは座席を配置できる空マスか,配置できない壁マスのいずれかである. 座席間の間隔を確保するため,各空マスに配置できる座席は高々ひとつである.

ここで,グリッドの北西角のマスから始めて,東または南に隣接する空マスに移ることを繰り返し, 南東角のマスに至る経路を「換気経路」と呼ぶことにする. 換気経路は一般には多数存在する. 座席を配置するどのマスについても,そこを通る換気経路が少なくともひとつは存在していなくてはならない. また,換気経路中の座席を配置するマスの数を「座席経由数」と呼ぶとき, どの換気経路の座席経由数もあらかじめ定められた許容最大値以下でなければならない. 上記の条件を満たしてなるべく多くの座席を配置する方法を考えて欲しい.

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

n m k
a1,1a1,m

an,1an,m

n, m はそれぞれグリッドの縦横のマスの数を表す. n, m は,正の整数であり,20 を超えない. k は座席経由数の許容最大値を表す. k は,正の整数であり,n + m − 1 を超えない. 続く n 行はそれぞれm 文字からなり, 各文字は '.' または '#' のいずれかである. グリッドの ij 列目のマスは ai,j が '.' なら空マス, '#' なら壁マスである. 第 1 行第 1 列が部屋の北西角,第 n 行第 m 列が南東角に対応する.

入力の終わりは三つのゼロからなる行で表される. データセットの個数は 100 を超えない.

Output

各データセットについて,以下の n + 1 行を出力せよ. まず,1 行目に配置できる座席の最大数を 1 行に出力せよ. 2 行目以降には具体的な座席数が最大となる配置のひとつを出力せよ. 配置の出力は入力と同様の形式とし, 座席を配置する空マスを '.' から '@' に変更したもので表せ. 最大数の座席を収容できる配置が複数存在する場合は, 各行の文字列を連結したときに ASCII 順序で辞書順最小になるものを求めよ. ASCII コードは '#' < '.' < '@' の順である.

Sample Input

3 3 3
...
.#.
...
3 3 1
...
.#.
...
6 11 1
...........
.....#.....
.....#.....
.....#.....
.....#.....
...........
7 7 3
.......
.##.##.
.#...#.
.#...#.
.#...#.
.##.##.
.......
0 0 0

Output for the Sample Input

6
.@@
@#@
@@.
2
...
.#@
.@.
10
..........@
....@#...@.
...@.#..@..
..@..#.@...
.@...#@....
@..........
9
.......
.##.##.
.#...#.
.#.@.#@
.#.@.#@
.##@##@
@@@....
(End of Problem G) A B C D E F G H