ページ

2012/04/23

[競技プログラミング][C言語][AtCoder]パズルのお手伝い

パズルのお手伝い

時間制限 : 2sec / スタックサイズの制限 : 10MB / メモリー制限 : 64MB

問題文

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


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

入力

入力は以下の形式で与えられる。
c11 c12 … c18
c21 c22 … c28
:
:
c81 c82 … c88
1 行目から 8 行目の各行は 8 文字の文字列が与えられる。
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版
エイトクイーン問題についても載っていたので
一体どうすればいいんだ…と行き詰まることがなかった。
通常のエイトクイーン問題とは少し異なるので
その部分を自分で変更してやればなんとか通るものの完成。
アルゴリズムとデータ構造って大事だね。