パズルのお手伝い
時間制限 : 2sec / スタックサイズの制限 : 10MB / メモリー制限 : 64MB問題文
高橋君は、パズルが好きです。今日は、8 クイーン問題に挑戦しようとしています。8 クイーン問題とは、8×8 のチェスボード上の縦・横・斜め 45 度の同一直線状に
それぞれクイーンが 1 つしか存在しないように、合計 8 つのクイーンを置く問題です。
高橋君は、3 つのクイーンを置いたところで残りのクイーンをどう置いたら良いのか判らなくなってしまいました。
残りの 5 つのクイーンを含めた 8 つのクイーンの位置を求めなさい。
入力
入力は以下の形式で与えられる。c11 c12 … c181 行目から 8 行目の各行は 8 文字の文字列が与えられる。
c21 c22 … c28
:
:
c81 c82 … c88
i 行目の先頭から j 番目の文字である cij は、i 行目 j 列目にクイーンが置かれているかどうかを表す。
cij は、'.' もしくは 'Q' で与えられ、
'.' であればクイーンが置かれていないことを、'Q' であればクイーンが置かれていることを表す。
出力
8 つのクイーンを置き終わった後の状態のうちの 1 つを、入力と同様のフォーマットで出力せよ。答えが存在しない場合は、"No Answer" と 1 行で出力せよ。
出典
パズルのお手伝い - AtCoder Regular Contest #001 | アットコーダー回答
AtCoder/arc001_3.cpp at master · wada811/AtCoder · GitHub持ってて良かったプログラミングの宝箱 アルゴリズムとデータ構造 第2版！
エイトクイーン問題についても載っていたので
一体どうすればいいんだ…と行き詰まることがなかった。
通常のエイトクイーン問題とは少し異なるので
その部分を自分で変更してやればなんとか通るものの完成。
アルゴリズムとデータ構造って大事だね。