BFSとは?
- 幅優先探索と呼ばれる経路探索のアルゴリズムです。
- 詳細は以下の記事などを参考にしてください。
到達可能かの判定
スタートからゴールまで到達できるかを判定するだけで、最短などを考慮しない場合です。
今回は斜め移動は不可能とします。
例題1(ゴールできる場合)
以下のグリッドを例に挙げて説明します。
〇は進行可能で、×は進行不可を示します。
また、各グリッドの状態を次の4色で示します。
| 色 | 状態 |
|---|---|
| 白 | 未調査 |
| 緑 | 調査済み(進行可) |
| 赤 | 調査済み(進行不可) |
(1)スタート地点(A1)の調査
まずは、スタート地点(A1)の近辺を調査します。調査の順番は、左⇒上⇒右⇒下とします。
順に調査すると、
| 左、上 | 範囲外(以下、壁と呼びます)なので除外 |
| 右 | 訪問可能 |
となるので、右側のB1に訪問(緑で塗りつぶし)します(下側は後回し)。
(2)B1の調査
次にB1の調査をしますが、| 左 | 訪問済み |
| 上 | 壁なので進行不可 |
| 右、下 | ×なので進行不可 |
となるため、これ以上探索は不要なことがわかります。
(3)スタート地点(A1)の調査2
B1からは探索不要なので(1)で未調査のA1の下側(A2)を調査して、進行可能であることを確認。(4)A2の調査
| 左 | 壁 |
| 上 | 訪問済み |
| 右 | xなので進行不可 |
| 下 | 進行可能 |
なので、次はA3を調査します。
結論
同様に調査すると、A3⇒B3⇒C3と到達できることが確認できます。
例題2(ゴールできない場合)
ゴールできない場合も確認します。
先ほどと同様のグリッドでA3がxに変化した場合は、(3)のA2調査時点で以下のようになりゴールできないことが分かります。
C++での実装
注意点は次の通り。
- 迷路(〇、×)を記録する2次元配列Sと色を管理する2次元配列seenを用意して、 seenには表に示す数値を格納。
- 探査の処理は再帰関数。
- 探査後にseenの右下(図ならC3)が1ならゴールできる、それ以外ならゴールできないと判定。
- xとyはその方向にも注意
| 数値 | 意味 |
|---|---|
| 0 | 未調査(白) |
| 1 | 調査済みで進行可(緑) |
| 2 | 調査済みで進行不可(赤) |
ソースコード
#include<iostream> #include<vector> int H, W; //2次元配列の幅と高さ std::vector<std::string> grid; //迷路の2次元配列(stringそのものがcharの配列として扱える) std::vector<std::vector<int>> seen; //調査状況(0:未探査、1：進行可、2:進行不可) // 進行可能かを判定 bool canEnter(int x, int y) { // 範囲を超えていないか if(x < 0 || W <= x || y < 0 || H <= y){ return false; } // 進行不可の場合 else if(grid[y][x] == 'x') { seen[y][x] = 2; return false; } // 進行可能 かつ 未訪問の場合は進行 else if(grid[y][x] == 'o' && seen[y][x] == 0){ seen[y][x] = 1; return true; } // それ以外なら進行不可 return false; } // 探索 void bfs(int x, int y) { // 右下に到達したら終了 if(y == H -1 && x == W -1){ return; } // 左 if(canEnter(x-1, y)) { bfs(x-1, y); } // 上 if(canEnter(x, y-1)) { bfs(x, y-1); } // 右 if(canEnter(x+1, y)) { bfs(x+1, y); } // 下 if(canEnter(x, y+1)) { bfs(x, y+1); } } int main(void){ // 幅と高さを入力 std::cin >> H >> W; // 迷路の入力 grid.resize(H); for (size_t i = 0; i < grid.size(); i++) { std::cin >> grid[i]; } // seenの要素をすべて0で初期化する seen.resize(H); for (size_t i = 0; i < seen.size(); i++) { seen[i].resize(W); for (int j = 0; j < W; j++) { seen[i][j] = 0; } } seen[0][0] = 1; // スタート地点は訪問したとする // 探索 int x = 0, y = 0; bfs(x, y); // seenの表示 std::cout << "seen" << std::endl; for (size_t i = 0; i < H; i++) { for (int j = 0; j < W; j++) { std::cout << seen[i][j]; } std::cout << std::endl; } // 右下が1なら到達 printf("結果 : "); if(seen[H-1][W-1] == 1){ printf("成功"); } else { printf("失敗"); } }
実行例
// 入力1(例題1と同じ) 3 3 oox oxx ooo // 結果1 seen 112 120 111 結果 : 成功 // 入力2(例題2と同じ) 3 3 oox oxx xoo // 結果2 seen 112 120 200 結果 : 失敗
