ルクの競プロ部屋

学生の競プロ生活を見たい人はどぞ

競プロ精選 100 問 by C++<幅優先探索>

精選100問

はじめに

今回は幅優先探索の6問をやりました！ 精選100問はこちら！

28　ALDS_11_C - 幅優先探索

問題はこちらです！
問題文↓

グラフを与えるので頂点1からの一番短い距離をBFSで求めてください

基本問題でした！
コードは以下のようになりました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

ll n;
vector<vector<ll>> graph;

// BFS
vector<ll> BFS(ll start)
{
    // 頂点の数だけ-1で初期化された配列を作る
    vector<ll> dist(n, -1);
    // 頂点startからの距離は0
    dist[start] = 0;
    // キューを作る
    queue<ll> que;
    // キューにstartを追加
    que.push(start);
    // キューが空になるまで繰り返す
    while (!que.empty())
    {
        // キューの先頭を取り出す
        ll v = que.front();
        que.pop();
        // vから行ける頂点をすべて調べる
        for (auto nv : graph[v])
        {
            // すでに発見済みの頂点は探索しない
            if (dist[nv] != -1)
                continue;
            // 新たな頂点nvについて距離情報を更新してキューに追加
            dist[nv] = dist[v] + 1;
            que.push(nv);
        }
    }
    return dist;
}

int main()
{
    // n個の頂点があるので、nを入力
    cin >> n;

    // 2次元配列のグラフを作る
    graph.resize(n);

    // n回繰り返して、u k v1,v2,v3...vkを入力
    rep(i, n)
    {
        ll u, k;
        cin >> u >> k;
        rep(j, k)
        {
            ll v;
            cin >> v;
            // グラフに辺を追加
            graph[u - 1].push_back(v - 1);
        }
    }
    // BFSを実行
    vector<ll> dist = BFS(0);

    // 各頂点までの距離を出力
    rep(i, n)
    {
        cout << i + 1 << " " << dist[i] << endl;
    }
    return 0;
}

29　AtCoder Beginner Contest 007 C - 幅優先探索

問題はこちらです！
問題文↓

地図を与えるので、sx,syからgx,gyまでの最短距離を出力してください

こちらも基本問題でした！
こんな感じです

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    // 入力.
    int h, w, sx, sy, gx, gy;
    cin >> h >> w >> sx >> sy >> gx >> gy;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    // BFSを実行する.
    vector<vector<int>> dist(h, vector<int>(w, -1));
    queue<pair<int, int>> q;
    q.push({sx - 1, sy - 1});
    dist[sx - 1][sy - 1] = 0;
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (int dx = -1; dx <= 1; dx++)
        {
            for (int dy = -1; dy <= 1; dy++)
            {
                if (dx == 0 || dy == 0)
                {
                    int nx = x + dx;
                    int ny = y + dy;
                    if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                        continue;
                    if (s[nx][ny] == '#')
                        continue;
                    if (dist[nx][ny] != -1)
                        continue;
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    cout << dist[gx - 1][gy - 1] << endl;
    return 0;
}

30　JOI 2011 予選 5 - チーズ

問題はこちらです！
問題文↓

初期座標・1からnまでの数字(1≦n≦9)・'.'+'X'という地面と障害物の書かれた地図を渡すので
初期座標から初めて、1,...,nと行くのに最小で何歩進めばよいかを求めてください

n回BFSを実行して、足し合わせればいいですね！
こんな感じに書きました！

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    // h,w,nを受け取る
    int h, w, n;
    cin >> h >> w >> n;
    // 地図を受け取る
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    // 現在地Sと'1'～'n'までの位置を記録する
    int Sx, Sy;
    vector<pair<int, int>> pos(n + 1);
    rep(i, h)
    {
        rep(j, w)
        {
            // 自分の初期位置.
            if (s[i][j] == 'S')
            {
                Sx = i;
                Sy = j;
            }

            // チーズの位置.
            if (s[i][j] >= '1' && s[i][j] <= '9')
            {
                pos[s[i][j] - '0' - 1] = make_pair(i, j);
            }
        }
    }

    // 現在地から初めて、1,...nまでの最短距離をBFSで求める
    int ans = 0;
    rep(i, n)
    {
        vector<vector<int>> dist(h, vector<int>(w, -1));
        queue<pair<int, int>> q;
        q.push(make_pair(Sx, Sy));
        dist[Sx][Sy] = 0;
        while (!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if (x == pos[i].first && y == pos[i].second)
            {
                ans += dist[x][y];
                Sx = x;
                Sy = y;
                break;
            }
            rep(j, 4)
            {
                int nx = x + (j == 0) - (j == 1);
                int ny = y + (j == 2) - (j == 3);
                if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                    continue;
                if (s[nx][ny] == 'X')
                    continue;
                if (dist[nx][ny] != -1)
                    continue;
                dist[nx][ny] = dist[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
    cout << ans << endl;
    return 0;
}

31　JOI 2012 予選 5 - イルミネーション

問題はこちらです！
問題文↓

六角形をつなぎ合わせたような図を作成する
このとき、黒い部分の周りの長さを求めよ


(画像は問題文より参照)
重要だと思ったことは2つありました
・偶数行・奇数行によって見る場所が変わること
・与えられた地図の周りに白色の土地を作成して、BFSをすること
です！
一度、周りに新しく土地を作って、BFSを実行することで、赤枠の外側の白色の六角形を判定することが出来ました
また、奇数行は上、下、右上、右下、左、右・偶数行は上、下、左上、左下、左、右というふうに見る場所が変わってきます
こんな感じのコードを書きました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    // h,w
    int h, w;
    cin >> w >> h;

    // aに周りに0を追加した配列を作成
    vector<vector<int>> a(h + 2, vector<int>(w + 2, 0));
    rep(i, h)
    {
        rep(j, w)
        {
            cin >> a[i + 1][j + 1];
        }
    }

    // a[0][0]から初めて、0と2は通れる、1は通れない
    // BFSで(0,0)から移動可能なマスを全て2に置き換える
    queue<pair<int, int>> q;
    q.push({0, 0});

    // ただし、地図は六角形の組み合わさったハニカム構造になっている
    // そのため、奇数行と偶数行で移動可能な方向が異なる
    // 奇数行は上、下、右上、右下、左、右
    // 偶数行は上、下、左上、左下、左、右
    auto directionX = vector<vector<int>>{
        {0, 0, -1, -1, -1, 1},
        {0, 0, 1, 1, -1, 1},
    };
    auto directionY = vector<vector<int>>{
        {-1, 1, -1, 1, 0, 0},
        {-1, 1, -1, 1, 0, 0},
    };
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        rep(i, 6)
        {
            int nextX = x + directionX[y % 2][i];
            int nextY = y + directionY[y % 2][i];
            if (nextX < 0 || nextX >= w + 2 || nextY < 0 || nextY >= h + 2)
            {
                continue;
            }
            if (a[nextY][nextX] == 0)
            {
                a[nextY][nextX] = 2;
                q.push({nextX, nextY});
            }
        }
    }

    // 全部のマスを見て、1があれば、その周りにある2の個数を数える
    int ans = 0;
    rep(i, h + 2)
    {
        rep(j, w + 2)
        {
            if (a[i][j] == 1)
            {
                rep(k, 6)
                {
                    int nextX = j + directionX[i % 2][k];
                    int nextY = i + directionY[i % 2][k];
                    if (nextX < 0 || nextX >= w + 2 || nextY < 0 || nextY >= h + 2)
                    {
                        continue;
                    }
                    if (a[nextY][nextX] == 2)
                    {
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

いい問題です！

32　AOJ 1166 - 迷図と命ず

問題はこちらです！
問題文↓

ブロック状の迷路でなく、線が書かれている迷路がある
その迷路の左上から右下への最短距離を求めよ

普通のBFS問題です！
ただ、移動できる場所に注意
コードはこんな感じに書きました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int h, w;
    cin >> w >> h;
    while (h != 0 && w != 0)
    {
        // 2 * h - 1行の配列を作成
        vector<vector<int>> field(2 * h - 1);
        rep(i, 2 * h - 1)
        {
            rep(j, w - !(i % 2))
            {
                int x;
                cin >> x;
                field[i].push_back(x);
            }
        }

        // BFSを実行
        vector<vector<int>> dist(h, vector<int>(w, -1));
        queue<pair<int, int>> que;
        que.push(make_pair(0, 0));
        dist[0][0] = 1;
        bool canG = false;
        while (!que.empty())
        {
            pair<int, int> p = que.front();
            que.pop();
            int x = p.first;
            int y = p.second;

            // ゴールに到達したら終了
            if (x == w - 1 && y == h - 1)
            {
                cout << dist[y][x] << endl;
                canG = true;
                break;
            }

            // 4方向に移動
            if (x > 0 && field[2 * y][x - 1] == 0 && dist[y][x - 1] == -1)
            {
                que.push(make_pair(x - 1, y));
                dist[y][x - 1] = dist[y][x] + 1;
            }
            if (x < w - 1 && field[2 * y][x] == 0 && dist[y][x + 1] == -1)
            {
                que.push(make_pair(x + 1, y));
                dist[y][x + 1] = dist[y][x] + 1;
            }
            if (y > 0 && field[2 * y - 1][x] == 0 && dist[y - 1][x] == -1)
            {
                que.push(make_pair(x, y - 1));
                dist[y - 1][x] = dist[y][x] + 1;
            }
            if (y < h - 1 && field[2 * y + 1][x] == 0 && dist[y + 1][x] == -1)
            {
                que.push(make_pair(x, y + 1));
                dist[y + 1][x] = dist[y][x] + 1;
            }
        }
        if (!canG)
        {
            cout << 0 << endl;
        }
        cin >> w >> h;
    }
    return 0;
}

33　AtCoder Beginner Contest 088 D - Grid Repainting

問題はこちらです！
問題文↓

迷路をクリアして、スタートからゴールまでの一方通行の道を作って、それ以外を黒色で埋めてください
もし、迷路がゴールできないのなら-1を出力してください

BFSを実行して、hw-(最短距離+1)-黒いマスの数で求まります！
以下のようになりました

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i < (n); ++i)
#define rrep(i, n) for (ll i = n; i > 0; --i)
#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define yesNo(b) ((b) ? "Yes" : "No")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const double pi = 3.141592653589793;
int smallMOD = 998244353;
int bigMOD = 1000000007;

int main()
{
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    // BFSで(1,1)から(h,w)までの最短距離を求める
    int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
    vector<vector<int>> dist(h, vector<int>(w, -1));
    queue<pair<int, int>> que;
    dist[0][0] = 0;
    que.push(make_pair(0, 0));
    while (!que.empty())
    {
        int y, x;
        tie(y, x) = que.front();
        que.pop();
        rep(dir, 4)
        {
            int ny = y + dy[dir], nx = x + dx[dir];
            if (ny < 0 || ny >= h || nx < 0 || nx >= w)
                continue;
            if (s[ny][nx] == '#')
                continue;
            if (dist[ny][nx] != -1)
                continue;
            dist[ny][nx] = dist[y][x] + 1;
            que.push(make_pair(ny, nx));
        }
    }
    if (dist[h - 1][w - 1] == -1)
    {
        cout << -1 << endl;
        return 0;
    }
    // すべてのマスから#の個数を数える
    int num = 0;
    rep(i, h) rep(j, w) if (s[i][j] == '#') num++;
    cout << h * w - (dist[h - 1][w - 1] + num) - 1 << endl;
    return 0;
}

おわりに

BFSが終わりました！
次からはDP問題です！
ではまた