蟻本 | 2-1 すべての基本 “全探索”

最近蟻本の初級編をやり直したのだが2-1と2-2の記事がなかったので一応貼り付けとく

部分和問題

bool dfs(int i, int sum) {
    if (i == n) {
        return sum == k;
    }
    if (dfs(i + 1, sum)) {
        return true;
    }
    if (dfs(i + 1, sum + a[i])) {
        return true;
    }
    return false;
}

void solve() {
    if (dfs(0, 0)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Lake Counting

int n, m;
char field[110][110];

void dfs(int x, int y) {
    //置き換える
    field[x][y] = '.';

    for (int dx = -1; dx <= 1; ++dx) {
        for (int dy = -1; dy <= 1; ++dy) {
            int nx = x + dx;
            int ny = y + dy;
            if (0 <= nx && nx < n && 0 <= ny && ny < m &&
                field[nx][ny] == 'W') {
                dfs(nx, ny);
            }
        }
    }
}

void solve() {
    int res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (field[i][j] == 'W') {
                dfs(i, j);
                res++;
            }
        }
    }
    printf("%d\n", res);
}

迷路の最短路

char maze[MAX_N][MAX_N + 1];
int n, m;
int sx, sy;
int gx, gy;

int d[MAX_N][MAX_N];

//移動４方向ベクトル
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

// (sx, sy)から(gx, gy)への最短距離を求める
// たどり着けないとINF
int bfs() {
    queue<P> que;
    //全ての点をINFで初期化
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            d[i][j] = INF;
        }
    }

    //スタート地点をqueに入れて距離を0にする
    que.push(P(sx, sy));
    d[sx][sy] = 0;

    //キューが空になるまでループ
    while (que.size()) {
        //キューの先頭を取り出す
        P p = que.front();
        que.pop();
        //ゴールなら終了
        if (p.first == gx && p.second == gy) {
            break;
        }
        //移動4方向ループ
        for (int i = 0; i < 4; ++i) {
            //移動した後の点を(nx, ny)とする
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];

            //移動が可能か
            //すでに訪れていないか
            if (0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny] != '#' &&
                d[nx][ny] == INF) {
                //移動できるならばキューに入れて、距離を代入
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }
    return d[gx][gy];
}

void solve() {
    int res = bfs();
    printf("%d\n", res);
}