ぷよぷよの解答の解説。

ぷよぷよの解答 - How to disappear completely
を紹介してみる。解説といいながら略解なので紹介と言いつつ詳解ではないのであしからず。


誰も得しないと思って書いたとかわざわざ言う事でもないですがもし誰かの役に立ったりしたらそれはとっても嬉しいなって。これが言いたかっただけとかそんな事はないです、はい。


struct Puyo
{
    char    type_;
    bool    searched_;
    bool    erased_;
};

type_ : ぷよの色。' 'で空白マス。空白マスとか書いてて気づいたけど、PuyoよりCellとかBlockとか言う名前の方が良かったかも。'$'はダミーの壁。

searched_ : searchされたかどうか。searchとはそのぷよと同じ色のぷよが4つ以上つながっているかどうかを探す処理のことです。
erased_ : eraseされるかどうか。searchされたときに4つ以上同じぷよがつながっていたら、そのぷよからつながった同じ色のぷよを縦横無尽にさがしてこれをセットします。

class Field
{
public:
    std::vector<std::vector<Puyo>>    data_;
};

Puyo構造体の縦横の2次元配列でフィールド。

PuyoとFieldがどんな感じか出力したいのでostreamとのoperator>>を定義しておきます


std::auto_ptr<Field> read_data(std::string const & filename);

ストリームでファイル開いて、行ごとにファイル全部読み込みます。
different_predとかいう何だその名前みたいなpredicateをつかって全部の行が同じ文字数かどうかチェックしてれう。ていうかこれBOOST_ASSERTにしてるけど普通にエラーですよね。

次にFieldに四方に'$'による壁を加えてぷよを格納していきます。空白はそのまま空白ですし、連鎖シミュレータ codename "\(^o^)/オワニモ"に対応するために'0'も空白セル扱いにしてます。

PSTADE_OVEN_FOREACHはBOOST_FOREACHに似ていますが、Rangeから取り出す値の型を推論してくれます。packは複数のRangeの組を作ってくれます。
dropped Range-adaptorは引数分の要素をRangeの先頭から除いたRangeを作ってくれます(元のRange自体は変更しない)。
popped Range-adaptorはRangeの最後の要素を除いたRangeを返してくれます。
zipped Range-adaptorはRangeの組から組のRangeを作ってくれます。
なのでここでは、

  1. ファイルから読み込んだ行の列と、Fieldのメンバ変数の行の列から先頭と末尾のダミーの行を除いたものの組を作って
  2. 行の組から組の行を作って
  3. PSTADE_OVEN_FOREACHで組を1つずつ取り出している

というわけです。
_1という適当な変数名で受け取った組の1番目の要素はpackに渡された1番目のRangeの要素で、_1の2番目の要素はpackに渡された2番目のRangeの要素です。

PSTADE_OVEN_FOREACHの中で、_1から値をとって、ファイルから読んだデータの方からPuyoの値をセットしています。壁にはbpという先に作った壁用のデータ入れてますね。なんでbpって名前にしたのか、今となっては誰も知らない。


int search(Field &f, size_t x, size_t y, Puyo const &p, int count);

フィールドと位置とその位置のPuyoとつながっている同じ色のPuyoの数をもらって、そこから先につながってる数と合わせた数を返します。再帰します。再帰でたどるPuyoには

司会の紳助が「我々スタッフが一生懸命、一生懸命探しました。お母さん見つかりましたよ」と語りかけ

嗚呼!バラ色の珍生!! - Wikipedia

searched_フラグをセットします。


void walk(Field &f, size_t x, size_t y, Puyo const &p);

erased_フラグがセットされたPuyoにつながった同じ色のPuyoを再帰的にerased_していきます。


bool prepare(Field &f);

4つ以上つながったPuyoが有ればその中で最初の探索の対象になったPuyoにerased_フラグセットしてwalk関数で再帰的にerased_セットしていきます。erased_がセットされたら変更が有ったとしてchangedにtrueがセットされますね。
探索の末Fieldに何にも変更がなければchangedはfalseのままです。
で、changedを返します。


void step(Field &f);

erased_なPuyoがあれば下方向に詰めていきます。


int main(int argc, char **argv);

setlocaleにNULL文字列を渡してシステムのデフォルトのロカールを設定しています。localeの発音はロケール派とロカール派がいるみたいですが

Pronunciation
(UK) IPA: /ləʊˈkɑːl/
Rhymes: -ɑːl
(US) IPA: /loʊˈkæl/
Rhymes: -æl

locale - Wiktionary

なので割とどっちでもいいですね。

read_dataから構築されたFieldもらって、prepereで変更が有ったらstepで消されるべきPuyoを消します。変更がなくなるまでちょくちょく状況を出力しながらループします。

以上。