LoginSignup
0
0

More than 3 years have passed since last update.

@RubyLrving(ruby lrving)

BFSを学ぶ

Posted at

AtCoder 版！蟻本 (初級編)

今日からAtCoder 版！蟻本 (初級編)の記事を読み進めましょう！
蟻本とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。

幅優先探索とは

深さ優先探索と同じく、一番最初の状態から遷移を繰り返すことで辿り着ける全ての状態を生成します。
異なるのは検索する順番です。
一回の遷移で検索できる場所→２回の遷移で探索できる場所...の順に検索をしていきます。

幅優先探索のテンプレート

C++
//Queueを生成
queue<P> que;
//最初の要素をキューに追加
que.push(P(sy, sx));

//キューの要素がなくまるまで処理を行う
while(que.size()){
    //最初の要素を取り出す
    P p = que.front();
    que.pop();
    //処理に適した繰り返し処理
    for(int i=0; i<4; i++){
        //何かしらの処理
        int ny = p.first + dy[i];
        int nx = p.second + dx[i];
        //キューに追加する条件
        if(....){
            //何かしらの処理

            //キューに追加
            que.push(P(ny, nx));
        }
    }
}

幅優先探索の基本

幅優先探索ではQueueを使用します。
開始地点から条件に適した近い場所だけ処理を行えます。

例題

例題 2-1-3　迷路の最短路

問題文は蟻本を見てください。(ここに記載すると著作権の問題が発生します。)

  • 迷路のフィールドと同じ大きさの配列を用意し、距離を格納します。
  • そのためにBFSを使用します。
  • スタート地点とゴール地点の座標を保持。
  • キューに追加された座標の上下左右から通路を判定し、キューに追加します。
  • キューに追加できるなら、現在の座標の距離に＋１した値を進む座標の距離に格納します。
C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
using namespace std;
using ll =long long;
using P = pair<int,int>;

#define INF 1000000000
#define MAX_H 100
#define MAX_W 100

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

int main(int argc, const char * argv[]) {

    int n, m;
    cin >> n >> m;

    char maze[MAX_H][MAX_W+1];
    int d[MAX_H][MAX_W];
    int sx, sy;
    int gx, gy;
    queue<P> que;

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> maze[i][j];
            d[i][j]=INF;
            if(maze[i][j] == 's'){
                sx = j;
                sy = i;
            }
            if(maze[i][j] == 'g'){
                gx = j;
                gy = i;
            }
        }
    }

    que.push(P(sy, sx));
    d[sy][sx] = 0;

    while(que.size()){
        P p = que.front();
        que.pop();

        if(p.first == gy && p.second == gx) break;

        for(int i=0; i<4; i++){
            int ny = p.first + dy[i];
            int nx = p.second + dx[i];

            if(0<=nx&&nx<m && 0<=ny&&ny<n && maze[ny][nx] != '#' && d[ny][nx] == INF){
                que.push(P(ny, nx));
                d[ny][nx] = d[p.first][p.second] + 1;
            }
        }
    }

    cout << d[gy][gx] << endl;

    return 0;
}

C - 幅優先探索

問題文はAtcoderを見てください。
蟻本の例題そのままですね。

C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#include<queue>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
using namespace std;
using ll =long long;
using P = pair<int,int>;

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

int main(int argc, const char * argv[]) {
    int r, c, sy, sx, gy, gx;
    cin >> r >> c;
    cin >> sy >> sx;
    cin >> gy >> gx;

    char field[50][50];
    int dist[50][50];

    for(int y=0; y<r; y++){
        string s;
        cin >> s;
        for(int x=0; x<c; x++){
            field[y][x]=s[x];
            dist[y][x]=-1;
        }
    }

    sy-=1;
    sx-=1;
    gy-=1;
    gx-=1;

    dist[sy][sx] = 0;
    queue<P> que;
    que.push(P(sx, sy));

    while(que.size()){
        P p = que.front();
        que.pop();

        for(int i=0; i<4; i++){
            int nx=p.first+dx[i];
            int ny=p.second+dy[i];

            if(0<=nx && nx<c && 0<=ny && ny<r && dist[ny][nx]<0 && field[ny][nx]=='.'){
                dist[ny][nx]=dist[p.second][p.first]+1;
                que.push(P(nx, ny));
            }
        }
    }

    cout << dist[gy][gx] << endl;

    return 0;
}

D - Grid Repainting

問題文はAtcoderを見てください。

  • 計算量はO(N)
  • 全ての.の数　ー　自分が通ったマスの数　＝　答え
  • 今回からrepを使用していきます。コードを書く量が少なければ実装が早くなります。
C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#include<queue>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
using namespace std;
using ll =long long;
using P = pair<int,int>;

#define MAX_H 50
#define MAX_W 50

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

int main(int argc, const char * argv[]) {

    int h, w;
    cin >> h >> w;

    char field[MAX_H][MAX_W];
    int dist[MAX_H][MAX_W];
    int change=0;

    rep(y, h){
        string s;
        cin >> s;
        rep(x, w){
            if(s[x]=='.') change++;
            field[y][x] = s[x];
            dist[y][x] = -1;
        }
    }

    queue<P> que;
    que.push(P(0,0));
    dist[0][0]=0;

    while(que.size()){
        P p = que.front();
        que.pop();

        rep(i, 4){
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];

            if(0<=nx && nx<w && 0<=ny && ny<h && field[ny][nx] == '.' && dist[ny][nx]==-1){
                dist[ny][nx] = dist[p.second][p.first]+1;
                que.push(P(nx, ny));
            }
        }
    }

    if(dist[h-1][w-1]>=0) cout << change - (dist[h-1][w-1] + 1) << endl;
    else cout << "-1" << endl;

    return 0;
}

A - Darker and Darker

問題文はAtcoderを見てください。

  • 開始地点が複数あるタイプです。
  • 開始地点の数をカウント、次の処理を行う数をカウント、...。
  • 一区切りごとに各種カウントを初期化、回数をカウント。
  • 特に難しい事はないかと思います。
C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#include<queue>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384


using namespace std;
using ll =long long;
using P = pair<int,int>;

#define MAX_H 1000
#define MAX_W 1000
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

char filed[MAX_H][MAX_W];
bool check_filed[MAX_H][MAX_W];

int main(int argc, const char * argv[]) {
    int h, w;
    cin >> h >> w;

    queue<P> que;
    rep(y, h){
        string s;
        cin >> s;
        rep(x, w){
            filed[y][x] = s[x];
            check_filed[y][x] = false;
            if(s[x] == '#'){
                que.push(P(x, y));
                check_filed[y][x] = true;
            }
        }
    }

    int que_size = (int)que.size();
    int que_size_next = 0;
    int count = 0;
    int res = 0;
    while(que.size()){
        P p = que.front();
        que.pop();

        rep(i, 4){
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];

            if(0<=nx&&nx<w&&0<=ny&&ny<h&&filed[ny][nx]=='.'&&check_filed[ny][nx]==false){
                check_filed[ny][nx] = true;
                que.push(P(nx, ny));
                que_size_next++;
            }
        }

        count++;
        if(count>=que_size){
            que_size = que_size_next;
            if(que_size_next>0) res++;
            count = 0;
            que_size_next = 0;
        }
    }

    cout << res << endl;
    return 0;
}

C - 器物損壊！高橋君

問題文はAtcoderを見てください。

  • bfsの応用問題です。
  • '.'を優先して処理を行う事、これだけ気をつけると解けます。
C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

#include<queue>
#define MAX_H 500
#define MAX_W 500

char field[MAX_H][MAX_W];
int dist[MAX_H][MAX_W];

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

int main(int argc, const char * argv[]) {
    int h, w;
    cin >> h >> w;

    int sx=0, sy=0;
    int gx=0, gy=0;

    rep(y, h){
        string s;
        cin >> s;
        rep(x, w){
            field[y][x] = s[x];
            dist[y][x] = -1;
            if(s[x] == 's'){
                sx=x;
                sy=y;
                dist[sy][sx] = 0;
            }else if(s[x] == 'g'){
                gx=x;
                gy=y;
            }
        }
    }

    deque<P> que;
    que.push_front((P(sx, sy)));

    while(que.size()){
        P p = que.front();
        que.pop_front();

        rep(i, 4){
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];

            if(0<=nx&&nx<w&&0<=ny&&ny<h&&dist[ny][nx]<0){
                if(field[ny][nx] == '.' || field[ny][nx] == 'g'){
                    dist[ny][nx] = dist[p.second][p.first];
                    que.push_front(P(nx, ny));
                }
                if(field[ny][nx] == '#'){
                    dist[ny][nx] = dist[p.second][p.first]+1;
                    que.push_back(P(nx, ny));
                }
            }
        }
    }

    // insert code here...
    cout << (dist[gy][gx]<3 ?"YES":"NO") << endl;

    return 0;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0