【競プロ】BFSを理解しよう

今日は有名なアルゴリズム、幅優先探索（breadth-first search, BFS）について取り上げます。このタイプの問題は競プロをやってる感じがあってとても楽しいです。例題を使って理解していきましょう。

1 ABC7 C問題幅優先探索
2 ABC88 D問題 Grid Repainting
3 終わりに

ABC7 C問題幅優先探索

このアルゴリズムは最短経路を求めるのに便利です。考え方は問題ページでかなり分かりやすく説明されているので、まずはそちらを読んでみてください。

スタートから近い方から順に距離を調べていくので、最終的にゴールに書き込まれる距離が求めるべき最短距離であることがわかるでしょう。

処理のイメージ図を書きます。
（座標は \(x,y\) で書いています。）

スタートのマスに近い方から1マスずつ進んで、そのマスを調べる対象としてキューに放り込んでいきます。

実装にはqueueとpairを使うのでその使い方だけ確認しておきます。

queue
int型のキューは、queue<int> q のように宣言できます。
代表的な操作はpush, front, pop, emptyです。
例えばq.push(1)と書くと、キューに1が入力されます。
q.front()と書くと、一番最初に追加した要素を取り出します。
q.pop()と書くと、一番最初に追加した要素を取り除きます。
q.empty()と書くと、キューが空かどうかを返します。
pair
pairは2つの変数をまとめて管理できます。int型の値を組を持つpairはpair<int,int> pで宣言できます。
p = make_pair(0,1)のようにすると、pairが代入できます。
p.first(), p.second()と書くと、pair型の変数の1, 2番目の要素が取り出せます。

ここまで分かれば、コードが読めると思います。先程の図の通り実装すると以下のようになります。

18,19行目の配列 \(dy,dx\) は以下の図の4つのベクトルの組を表し、これを使って座標の移動を簡潔に表せます。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main(){
    int r,c;
    cin >> r >> c;
    int sy,sx,gy,gx;
    cin >> sy >> sx >> gy >> gx;
    sy--; sx--; gy--; gx--;
    vector<vector<char>> maze(r,vector<char>(c,'#'));
    rep(i,r) rep(j,c) cin >> maze[i][j];

    vector<vector<ll>> d(r,vector<ll>(c,INF));
    queue<pair<int,int>> q;
    vector dy = {0,1,0,-1};
    vector dx = {1,0,-1,0};
    d[sy][sx] = 0;
    q.push(make_pair(sy,sx));
    while(!q.empty()){
        int y = q.front().first, x = q.front().second;
        if(y == gy && x == gx) break;
        rep(i,4){
            int ny = y+dy[i], nx = x+dx[i];
            if(maze[ny][nx] == '.' && d[ny][nx] == INF){
                d[ny][nx] = d[y][x] + 1;
                q.push(make_pair(ny,nx));
            }
        }
        q.pop();
    }
    cout << d[gy][gx] << endl;
    return 0;
}

探索済みのところにはINFを入れておきます。そうしないと、遠回りしてそのマスを調べる場合も値が更新されてしまします。

ABC88 D問題 Grid Repainting

先ほどとほぼ同じです。復習のつもりで1から実装して見てください。一度できれば、あとは脳死で書けるようになると思います。

以下が提出コードです。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main(){
	int h,w;
	cin >> h >> w;
	vector<vector<char>> grid(h,vector<char>(w));
	int cnt_black = 0;
	rep(i,h) rep(j,w){
		cin >> grid[i][j];
		if(grid[i][j] == '#') cnt_black++;
	}
	
	vector<int> dy = {0,1,0,-1};
	vector<int> dx = {1,0,-1,0};
	vector<vector<ll>> d(h,vector<ll>(w,INF));
	queue<pair<int,int>> q;
	q.push(make_pair(0,0));
	while(!q.empty()){
		int y = q.front().first, x = q.front().second;
		rep(i,4){
			int ny = y+dy[i], nx = x+dx[i];
			if(y == h-1 && x == w-1)
				break;
			if(ny < 0 || ny > h-1 || nx < 0 || nx > w-1)
				continue;
			if(grid[ny][nx] == '.' && d[ny][nx] == INF){
				d[ny][nx] = d[y][x]+1;
				q.push(make_pair(ny,nx));
			}
		}
		q.pop();
	}

	if(d[h-1][w-1] == INF){
		cout << -1 << endl;
		return 0;
	}
	int ans = h*w - cnt_black - (d[h-1][w-1]+1);
	cout << ans << endl;
	return 0;
}

先ほどは迷路が壁で囲まれていたのでチェックしませんでしたが、調べるマスが範囲外にならないように確認しましょう。