AtCoder Regular Contest 001

C - パズルのお手伝い


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 64MB

問題文

高橋君は、パズルが好きです。今日は、8 クイーン問題に挑戦しようとしています。
8 クイーン問題とは、8×8 のチェスボード上の縦・横・斜め 45 度の同一直線状にそれぞれクイーンが 1 つしか存在しないように、合計 8 つのクイーンを置く問題です。


図:出力例1の図。縦・横・斜め 45 度の同一直線状にそれぞれクイーンが 1 つのみ存在する。

高橋君は、3 つのクイーンを置いたところで残りのクイーンをどう置いたら良いのか判らなくなってしまいました。
残りの 5 つのクイーンを含めた 8 つのクイーンの位置を求めなさい。

入力

入力は以下の形式で与えられる。
c_{11} c_{12}c_{18} 
c_{21} c_{22}c_{28}
:
:
c_{81} c_{82}c_{88}
  • 1 行目から 8 行目の各行は 8 文字の文字列が与えられる。
  • i 行目の先頭から j 番目の文字である c_{ij} は、i 行目 j 列目にクイーンが置かれているかどうかを表す。
  • c_{ij} は、'.' もしくは 'Q' で与えられ、'.' であればクイーンが置かれていないことを、'Q' であればクイーンが置かれていることを表す。

出力

8 つのクイーンを置き終わった後の状態のうちの 1 つを、入力と同様のフォーマットで出力せよ。
答えが存在しない場合は、"No Answer"1 行で出力せよ。

入力例 1

........
........
.......Q
........
..Q.....
........
.Q......
........

出力例 1

Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....
  • 上記のようにクイーンを置いた時、条件を満たすことが出来ます。

入力例 2

.....Q..
.Q......
........
........
........
Q.......
........
........

出力例 2

No Answer
  • 初期配置で既に 1 行目と 6 行目のクイーンが斜め 45 度の同一直線状に存在するので、この地点で条件を満たしておらず答えは存在しません。

Source name

ARC 001

Submit提出する