C - パズルのお手伝い
Editorial
/ 
高橋君は、パズルが好きです。今日は、8 クイーン問題に挑戦しようとしています。
8 クイーン問題とは、8×8 のチェスボード上の縦・横・斜め 45 度の同一直線状にそれぞれクイーンが 1 つしか存在しないように、合計 8 つのクイーンを置く問題です。
図:出力例1の図。縦・横・斜め 45 度の同一直線状にそれぞれクイーンが 1 つのみ存在する。
高橋君は、3 つのクイーンを置いたところで残りのクイーンをどう置いたら良いのか判らなくなってしまいました。
残りの 5 つのクイーンを含めた 8 つのクイーンの位置を求めなさい。
入力は以下の形式で与えられる。
8 つのクイーンを置き終わった後の状態のうちの 1 つを、入力と同様のフォーマットで出力せよ。
答えが存在しない場合は、
/ 
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
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'であればクイーンが置かれていることを表す。
出力
答えが存在しない場合は、
"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 度の同一直線状に存在するので、この地点で条件を満たしておらず答えは存在しません。