深さ優先探索(DFS: Depth-First Search) -競技プログラミング初級問題-

この記事はOthloTech Advent Calendar 2016の12日目の記事です。

こんにちは、Code for Nagoya名誉代表の一人である遠山竜也です。
Othlotechのやすくんに、是非Advent Calendarを書いて欲しいと頼まれ、
競技プログラミングを少しだけかじってたことを生かして、記事を書きたいと思います。

深さ優先探索 (DFS: Depth-First Search)

深さ優先探索は、全探索の手法の最も有名なアルゴリズムなのでご存知の方も多いと思いますが、実装できますか？

グリッド上の経路探索におけるDFS

現在の地点$p=(x_p, y_p)$から四方八方に行き先があるような問題はどのようにDFSで記述したらいいのでしょうか？

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

int dfs(int x, int y){

    // 周囲4方位のマスを探索
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        dfs(nx, ny);
    }
}

このとき、以下のようにdx[]やdy[]などの配列を用いて各方位1マス先の座標を計算し、順にそのマスにおける処理をしていくとスッキリ記述できます。
ちなみに、配列d[]一つでdx[]とdy[]の両方の役目を持たすことができます。

• d[5] = { 0, 1, 0, -1, 0};
• d[4] = { 0, 1, 0, -1}; など

これらは、今回の記事からそれるので触れませんが、興味がある方は考えてみてください！

グリッド探索のためのグリッド情報の管理

2次元配列などを使って、グリッドの状態を管理する際に、間違って添字-1へアクセスしてしまうなどちゃんと管理しないとバグが発生してしまいます。

では、いっその事、外側1マスを壁のように限界を超えているかどうかの判定用に用意してしまうのもいいでしょう！

const int N = 20;

int main(){
    int state[N+2][N+2];
    memset(state, -1, sizeof(state)); // state[][]を全て-1で初期化

    /* これ以降、state[][]にグリッド情報を入力 */
}

今回は、$-1$を盤外判定用として使うため、memset()関数を用いることができます。
※memset()関数は1byte単位でメモリ領域を埋める関数。
→多次元配列を-1(すべてのビットが1)または0(すべてのビットが0)に簡単に初期化することができる。

ACM-ICPC 2006 国内予選 D問題: Curling 2.0

問題文&オンラインジャッジ: AOJ1144

2016年現在、学生の皆さんはポケモン金銀やルビー・サファイヤ(RS)の世代でしょうか？
ポケモンで思い出されるのは、そう、壁に当たるまで等速直線運動を強いられる氷の床！
金銀でいえば「こおりのぬけみち」、RSでいえば「あさせのほらあな」ですよ！
なかなか目的地に着くことができずに歯がゆい思いをした方もいらっしゃるのではないですか？

AOJ1144に問題文とオンラインジャッジ(AIZU ONLINE JUDGE)あるので、是非、苦戦してください！

aoj1144.cpp

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

// それぞれの状態を列挙型で表現（11以上は失敗のため、Failure=100）
enum{ Nothing, Barrier, Start, Goal, Failure = 100 };

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

int state[22][22]; // 大きく確保して、外側1つ分以上を盤外(-1)でとる

/*
 深さ優先探索(x,y: 現在位置、c:現在のコスト)
*/
int dfs(int x, int y, int c){
    // 11以上深く行く必要はないためFailure
    if (c > 10) return Failure;

    for (int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        // 障害物ならそちら側に滑らせられない
        if (state[nx][ny] == Barrier) continue;

        //state[nx][ny] == Nothing
        while (!state[nx][ny]){
            nx += dx[i], ny += dy[i]; // 何かが来るまで同じ方向に滑らせる
        }

        if (state[nx][ny] == Goal){
            return c + 1;
        }
        // 障害物ならもう一つ深く探索
        else if (state[nx][ny] == Barrier){
            state[nx][ny] = Nothing; // 一度障害物を除去

            // 探索してみて最小値を確保
            // 衝突する壁の一つ前に止まるため、nx-dx[i],ny-dy[i]
            int temp = dfs(nx - dx[i], ny - dy[i], c + 1);
            result = min(result, temp);

            // 探索終わったら、別の探索に影響を及ぼさないように障害物を直す
            state[nx][ny] = Barrier;
        }
    }
    return result;
}

int main(){
    while (1){
        int w, h; cin >> w >> h; //width, heignt
        if (!w && !h) break;

        result = Failure;
        int sx, sy;

        // state[][]を全て-1で初期化
        memset(state, -1, sizeof(state));
        // 入力
        for (int i = 1; i <= h; i++){
            for (int j = 1; j <= w; j++){
                cin >> state[i][j];

                if (state[i][j] == Start){
                    sx = i; sy = j; // スタートを確保
                    state[i][j] = Nothing;
                }
            }
        }

        int cnt = dfs(sx, sy, 0);
        if (cnt <= 10) cout << cnt << endl;
        else cout << -1 << endl;
    }
}