はじめに
迷路の探索問題ってBFSやDFSを知っていればアルゴリズム自体は単純ですが、通常のグラフより実装が面倒くさい。もうライブラリ化しても良いんじゃないかと思い、作ってみました。Atcoderだと以下の問題とかですね。
他にも何問かあったはず。
概要
２次元の迷路問題を解くライブラリです。C＋＋を使用しています。迷路問題はDFS（深さ優先探索）でも解けますが、今回はBFS（幅優先探索）での実装にしました。迷路をBFSじゃなくDFSで解かないといけない状況ってあります？
ライブラリ
今回作成したライブラリの全容は以下です
// Solving a maze using bfs
# define WALL '#'
# define PATH '.'
class coord{
public:
coord(){}
coord(int _x,int _y):x(_x),y(_y){}
int x,y;
};
class maze{
public:
maze(int _h,int _w):h(_h),w(_w){
m = vector<vector<char>>(h,vector<char>(w));
d = vector<vector<int>>(h,vector<int>(w,-1));
}
void input_map(){
rep(i,h){
string si; cin >> si;
rep(j,w){
m[i][j] = si[j];
if(si[j]==WALL) wall_n++;
if(si[j]==PATH) path_n++;
}
}
}
void set_start(coord _s){ s = _s; }
void calc_distance(){
queue<coord> q;
q.push(s);
d[s.x][s.y]=0;
while(q.size()){
coord u = q.front(); q.pop();
rep(ix,3)rep(jx,3){
if(abs(ix-1)+abs(jx-1)==2) continue;
int i = ix-1 + u.x;
int j = jx-1 + u.y;
if(i>=0&&i<h&&j>=0&&j<w&&d[i][j]==-1&&m[i][j]==PATH){
d[i][j] = d[u.x][u.y]+1;
q.push(coord(i,j));
}
}
}
}
int distance(coord g){return d[g.x][g.y];}
int number_of_wall(){return wall_n;}
int number_of_path(){return path_n;}
void print_map(){
rep(i,h){
rep(j,w) cout << m[i][j];
cout << endl;
}
}
void print_distance(){
rep(i,h){
rep(j,w) cout << d[i][j] << " ";
cout << endl;
}
}
private:
int h,w;
vector<vector<char>> m;
vector<vector<int>> d;
coord s;
int wall_n = 0;
int path_n = 0;
};
簡単に解説していきます。
入力について
本ライブラリでは、以下のような入力を前提としています。
h w
ccc
ccc
ccc
例えば以下のような入力です。
3 3
..#
# ..
...
これに合致しない問題の場合には、ライブラリを多少書き直す必要があります。
coordクラス
coordクラスは迷路の座標を表すクラスです。
class coord{
public:
coord(){}
coord(int _x,int _y):x(_x),y(_y){}
int x,y;
};
まあpair<int,int>でも良いんですが、何となくかっこいいからこれを使います。
メンバ変数
メンバ変数について説明します。
private:
int h,w;
vector<vector<char>> m;
vector<vector<int>> d;
coord s;
int wall_n = 0;
int path_n = 0;
| 変数名 | 説明 |
|---|---|
| h | 迷路の高さ（height） |
| w | 迷路の幅（width） |
| m | 通れる道や壁の情報 |
| d | スタート地点からの最短距離 |
| s | スタート地点 |
| wall_n | 壁の数 |
| path_n | 通れる道の数 |
初期化
コンストラクタです。
maze(int _h,int _w):h(_h),w(_w){
m = vector<vector<char>>(h,vector<char>(w));
d = vector<vector<int>>(h,vector<int>(w,-1));
}
迷路の高さと幅を引数として与えてやります。最短距離の初期値は-1とします。
迷路情報の入力
迷路情報は複数のchar型によって与えられるものとします。void input_map()はこれを読み込む関数です。
void input_map(){
rep(i,h){
string si; cin >> si;
rep(j,w){
m[i][j] = si[j];
if(si[j]==WALL) wall_n++;
if(si[j]==PATH) path_n++;
}
}
}
WALLとPATHは壁と道を表す文字列です。壁は#、道は.で設定されていることが多いので、デフォルトは#と.です。
スタート位置の設定
当たり前ですが、迷路を解くにはスタート地点が必要です。スタート地点はcoord型で入力します。
void set_start(coord _s){ s = _s; }
幅優先探索
本ライブラリのメインです。幅優先探索がよくわからない方は以下をご参照ください。
void calc_distance(){
queue<coord> q;
q.push(s);
d[s.x][s.y]=0;
while(q.size()){
coord u = q.front(); q.pop();
rep(ix,3)rep(jx,3){
if(abs(ix-1)+abs(jx-1)==2) continue;
int i = ix-1 + u.x;
int j = jx-1 + u.y;
if(i>=0&&i<h&&j>=0&&j<w&&d[i][j]==-1&&m[i][j]==PATH){
d[i][j] = d[u.x][u.y]+1;
q.push(coord(i,j));
}
}
}
}
if(abs(ix-1)+abs(jx-1)==2) continue;は斜め移動を禁止することを表しています。int i = ix-1 + u.x;は少しわかりにくいですが、u.x（今いるx座標）から-1、0、１マス移動した位置を意味しています。同様に、jはy座標について-1、0、１マス移動した位置を意味しています。
距離の出力
スタート地点から迷路内の任意の座標への最短距離は以下の関数で取得できます。
int distance(coord g){return d[g.x][g.y];}
画面への出力
それぞれの座標における迷路情報や最短距離の出力は以下で行えます。
void print_map(){
rep(i,h){
rep(j,w) cout << m[i][j];
cout << endl;
}
}
void print_distance(){
rep(i,h){
rep(j,w) cout << d[i][j] << " ";
cout << endl;
}
}
主にデバッグ用なので、必要な場面は少ないかもしれません。
まとめ
競技プログラミングでよく見る迷路探索問題をライブラリ化しました。
ご参考になれば幸いです！