Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

ABC088-D「Grid Repainting」(400)

※この記事は1ヶ月前にlivedoor Blogに上げたものの移転記事になります。

 

問題リンク:D - Grid Repainting

解説3問目。 こちらもリアルタイムでアタックして、方針まで合ってたのにTLEで通せなかった悲しい問題。 昨日(5/5)行われたABC096のC問題「Grid Repainting 2」の元ネタだったりもする。

幅優先探索という競プロでは基本となるテクニックの良い練習問題でもあるので、「幅優先探索?なにそれ?」って方にはこの機会に是非アタックしていただきたい。 

目次

問題概要

H*Wのマスが黒か白かに塗られている。 この盤面の(1, 1)にプレイヤーがおり、上下左右1マスの移動のみを繰り返して 「黒マスを一度も通らずに」(H, W)に辿り着けたらゲームクリアとなる。

ゲーム開始前、プレイヤーは好きなだけ白マスを黒に塗り替えることができ、その状態でゲームクリアができればその塗り替えたマスの数がプレイヤーのスコアとなる。

このとき、プレイヤーが得ることができる最大スコアを出力せよ。ただし、どのように塗ってもゲームクリアができないならば「-1」を出力せよ。

以下に一例を示す。

f:id:misteer:20180606023355j:plain

解法

やること

さて、まずは「どうすれば最大スコアを求められるか」を考える必要がある。

できるだけ多くのマスを黒に塗りたいわけだから、当然「通るマス以外は全部黒く塗る」べきだ。そこで、順番を逆転させて「まずは経路から考えて、そのあと通らなかったマスを全部黒に塗る」としても何ら問題ないのはお分かりだろう。

ともすれば、できるだけ通るマスの少ない経路を考えることになる。 つまりこの問題は、「迷路の最短経路を求めろ」という問題に言い換えることができるわけだ。

 

さて、やるべきことは分かった。 しかし迷路の最短経路なんてどうやって求めればいいのか? 実はこの手の問題には「特効薬」とでも言うべき有名なアルゴリズムが存在する。 それが幅優先探索 (Breath First Search、BFS)」である。

幅優先探索とは?

これを読んでいる人の中には「そもそもさっきから言ってる幅優先探索って何?」という人も少なくないだろう。 とはいえ、ここで手短にまとめられるほど簡単なアルゴリズムでもないので、参考となりそうなリンクを投げて説明は棚上げにさせていただく。

 

 

その他、かの有名な「蟻本」こと「プログラミングコンテストチャレンジブック」の序盤にも極めて丁寧に取り上げられている。初心者には少し重すぎるかもしれないが、大いに為になるので持っている方は根気よく読むことをオススメする。

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

 

実装

外部サイトに説明を丸投げしてしまったが、解答を実装していこう。

まずは初期化、そして解答出力の部分から作る。

int main() {
    int H, W;
    cin >> H >> W;

    string S[H];
    int wnum = 0;
    // white number: '.'(白マス)の数を数える
for (int i = 0; i < H; i++) { cin >> S[i]; for (int j = 0; j < W; j++) {
// 各行の'.'(白マス)を数える if (S[i][j] == '.') wnum++; } } // 幅優先探索で最短経路を出す // 最短経路長をdとする cout << wnum - d << endl; // wnumが初期の白マス数 // dは最短経路長=残すべき白マス数 return 0; }

ここで注意すべきは、初期化の時点で座標が1-indexedから0-indexedへ変わっているということ。 つまりスタート地点はS[0][0]、ゴール地点はS[H-1][W-1]となる。 ここを意識していないと後々バグに悩まされることになる。

 

それでは、いよいよ探索部分の実装に入る。

まず、幅優先探索では「次に訪れる予定の場所」を蓄えておく容器が必要になる。 さらに性質上、できるだけ早く入れたものは早めに取り出したい(これを「先入れ先出し」、FIFO(First in First out)と言ったりする)。

アナロジーを使えば、ちょうど下図の紙コップホルダーみたいなイメージである。 新しく訪れたい場所があれば上から座標を突っ込んで、入れた順に下から取り出して座標を見ていく。そしてホルダーが空になったら探索終了となる。

f:id:misteer:20180606021823j:plain

そんな機能を実現するために存在するデータ構造が「queue」と呼ばれるコンテナである。C++では、

#include <queue>

と宣言することで使用できるようになる。 大半のプログラミング言語ではライブラリが用意されているはずなので、各自調べていただきたい。

 

ではqueueを使って実装していこう。まずは(1, 1)から各マスへの最短距離を記録する二次元配列dを用意する。 最初にd[0][0]は1、他の点はまだ着いてないのでINFで初期化する。 そしてqueueに最初に訪れるべき点、つまり(0, 0)を突っ込む。

    int INF = 1 << 30;
    // 十分大きければなんでもいいが、オーバーフローに注意

    vector<vector<int>> d(H, vector<int>(W, INF));
    // (0, 0)からの最短距離を記録する
    // サイズはH*W、要素は全部INF

    queue<pair<int, int>> q;
    // 訪れるべき点を蓄える

    // 初期化
    d[0][0] = 1;
    q.push({0, 0});

続いて探索部を書く。主な流れは以下の通り:

  • qの先頭要素を取り出して削除する。
  • 周囲4マスについて、
    • マスは盤面に入っているか?(境界判定)
    • マスは白マスか?
    • 最短距離は更新されるか?
    をチェックする。
  • 全部満たすなら、
    • 最短距離を更新する。
    • マスをqueueに追加する。
  • これをqueueが空になるまで(=全マスの最短距離が求まるまで)行う

 上のリストを見ながら、まだ解いてない人は是非実装に挑戦して貰いたい。

そしてこれらを実装したものがこちら。

    int dx[4] = {0, -1, 1, 0};
    int dy[4] = {-1, 0, 0, 1};
    // 周囲4マスを見るときに使う(後ほど解説)

    while (!q.empty()) {
        // qの先頭データを取り出す
        pair<int, int> p = q.front();
        int x = p.front;
        int y = p.second;

        // qの先頭を削除
        q.pop();

        // dx[4]とdy[4]を使って周囲4マスを見る
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 境界判定((nx, ny)が盤面に入っているか)
            if (nx >= 0 && nx < H && ny >= 0 && ny < W) {
// 白マスかつ最短経路か判定 if (S[nx][ny] == '.' && d[x][y] + 1 < d[nx][ny]) {
// 最短経路更新 d[nx][ny] = d[x][y] + 1; // 「訪れるべき点」に追加 q.push({nx, ny}); } } } }

上で注目して頂きたいのがdx[4]とdy[4]である。 一目では何をしているか分からないかもしれないが、この配列によってスムーズに周囲4マスを見ることができる。イメージを下に示す。

f:id:misteer:20180606022014p:plain

随分と長くなってしまったが、このように幅優先探索は実装量がそこそこ多い。 「これを大会中に実装するの?」と不安になるかもしれないが、慣れればどうということはない。

なんならライブラリとして保存して、使うときはコピペするだけという状態にしておくのも悪くはない。しかし、最初のうちは毎回自分で書いてコードの動きを把握することをオススメする。

解答例

というわけで、これらを全て繋げると以下の通り。

int main() {
    int H, W;
    cin >> H >> W;

    string S[H];
    int wnum = 0;

    for (int i = 0; i < H; i++) {
        cin >> S[i];
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '.') wnum++;
        }
    }

    int INF = 1 << 30;
    vector<vector<int>> d(H, vector<int>(W, INF));

    queue<pair<int, int>> q;

    d[0][0] = 1;
    q.push({0, 0});

    int dx[4] = {0, -1, 1, 0};
    int dy[4] = {-1, 0, 0, 1};

    while (!q.empty()) {
        pair<int, int> p = q.front();
        int x = p.first;
        int y = p.second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < H && ny >= 0 && ny < W) {
                if (S[nx][ny] == '.' && d[x][y] + 1 < d[nx][ny]) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }

    if (d[H - 1][W - 1] == INF) {
        // 訪れなかった=ゴール不可能
        cout << -1 << endl;
    } else {
        cout << wnum - d[H - 1][W - 1] << endl;
    }

    return 0;
}

これで無事ACとなる。お疲れ様でした。

関数化

幅優先探索の部分を関数にした方が再利用性が高くなるので、そのバージョンも上げておく。

int H, W;
string S[50];

const int INF = 1 << 30;
const int dx[4] = {0, -1, 1, 0};
const int dy[4] = {-1, 0, 0, 1};

// 境界判定用関数
bool inarea(int x, int y) {
    return x >= 0 && x < H && y >= 0 && y < W;
}

// 幅優先探索部分を抽出
int bfs() {
    vector<vector<int>> d(H, vector<int>(W, INF));
    queue<pair<int, int>> q;

    d[0][0] = 1;
    q.push({0, 0});

    while (!q.empty()) {
        pair<int, int> p = q.front();
        int x = p.first;
        int y = p.second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (!inarea(nx, ny)) continue;
            // ネストを減らす

            if (S[nx][ny] == '.' && d[x][y] + 1 < d[nx][ny]) {
                d[nx][ny] = d[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    return d[H - 1][W - 1];
}

int main() {
    cin >> H >> W;

    int wnum = 0;
    for (int i = 0; i < H; i++) {
        cin >> S[i];
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '.') wnum++;
        }
    }

    int d = bfs();
    // ここで関数呼び出し、dにゴールまでの距離が入る

    if (d == INF) {
        cout << -1 << endl;
    } else {
        cout << wnum - d << endl;
    }
    return 0;
}

関数にするか埋め込むかは正直好みによるところが大きい。 関数にすればmain関数内がスッキリする。その一方で内容を追うためにコードを遡る必要があり、一部変数をグローバルにする事案も発生する。

しかし幅優先探索と対をなす「深さ優先探索(Depth First Search、DFS)」は再帰関数でないと書くのが難しいので、そちらに合わせるというのも悪くない。

感想

典型 of 典型な幅優先探索の問題なので、400点としては下位レベルだろうか。 しかし実装練習としては打ってつけなので、とくに幅優先探索を知らないという人はぜひチャレンジして頂きたい。

なお、過去のABC007-C「幅優先探索」がその名の通り幅優先探索のeditorial的な問題なので、そちらからアタックした方が良いかもしれない。

幅優先探索は実装方法に個人差があるアルゴリズムなので、他人の提出を眺めながら自分にあった実装方法を見つけ出すといいだろう。

余談

例によって今回書いたコード、及び過去に私が書いたコードのリンクを以下に貼っておく。参考までに。

あと解説して欲しい問題を随時募集しています。 ここのコメントかTwitterなどでお気軽にお申し付けください。