Recursive function memo at ATC001. Depth First Search(深さ優先探索)

feb28.cpp

#include <iostream>
#include <vector>

/*
DFS: depth-first search
          1
         /|\
       2  7  8
      / \    | \
    3     6  9  12
   / \       | \
 4     5    10  11
 
再帰あり
function 深さ優先探索(v)
    v に訪問済みの印を付ける
    v を処理する
    for each v に接続している頂点 i do
        if i が未訪問 then
            深さ優先探索(i)
*/

int H, W, max_depth;
std::pair<int, int> start, goal;
std::vector<std::vector<char>> town;
std::vector<std::vector<bool>> checked; 

// 次の探索場所への距離を全通り　上　右　下　左　（斜めは移動できない前提があるのでこれで全て）
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

/* Depth First Search */
bool dfs(std::pair<int, int> state, int result_depth) {
  // 訪問先をtrueにする
  checked.at(state.first).at(state.second) = true;
  /* Base */
  // 指定した深さを超えるとfalseを返す
  if(result_depth > max_depth) {
    std::cout << "depth over" << std::endl;
    return false;
  }
  // goalが探索済みならtrueを返す
  if(checked.at(goal.first).at(goal.second)) {
    printf("depth = %d\n", result_depth);
    return true;
  }
  
  /* Recursive */
  for(int i = 0; i < 4; i++) {
    // 移動先を探すため上下左右を判定する
    int ny = state.first + dy[i];
    int nx = state.second + dx[i];
    // 正しい移動か判定。正しくないなら次へ
    if(ny < 0 || H <= ny || nx < 0 || W <= nx) continue;
    // if(town.at(ny).at(nx) == '#') continue;
    if(checked.at(ny).at(nx)) continue;
    
    // 正しい移動先のny,nxを新しい頂点としてdfs()関数に入力
    if(dfs(std::make_pair(ny, nx), result_depth+1)) return true;
  }
  return false;
}

int main() {
  std::cin >> H >> W;
  town.assign(H, std::vector(W, '.'));
  checked.assign(H, std::vector(W, false));
  max_depth = 50; // 深度制限
  for(int y = 0; y < H; y++) {
    for(int x = 0; x < W; x++) {
      std::cin >> town.at(y).at(x);
      if(town.at(y).at(x) == '#') checked.at(y).at(x) = true; // 壁を探索済みにすることで関数内の記述を減らす
      if(town.at(y).at(x) == 's') start = std::make_pair(y, x); // start座標のペアを作る
      if(town.at(y).at(x) == 'g') goal = std::make_pair(y, x); // goal座標のペアを作る
    }
  }
  if(dfs(start, 0)) std::cout << "Yes" << std::endl;
  else std::cout << "No" << std::endl;
}

/*
input

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

output

depth = 50
Yes
*/

ACバージョン

#include <iostream>
#include <vector>

int H, W;
std::pair<int, int> start, goal;
std::vector<std::vector<char>> town;
std::vector<std::vector<bool>> checked; 

// 次の探索場所への距離を全通り　上　右　下　左　（斜めは移動できない前提があるのでこれで全て）
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

/* Depth First Search */
bool dfs(std::pair<int, int> state) {
  // 訪問先をtrueにする
  checked.at(state.first).at(state.second) = true;
  /* Base */
  // goalが探索済みならtrueを返す
  if(checked.at(goal.first).at(goal.second)) {
    return true;
  }
  
  /* Recursive */
  for(int i = 0; i < 4; i++) {
    // 移動先を探すため上下左右を判定する
    int ny = state.first + dy[i];
    int nx = state.second + dx[i];
    // 正しい移動か判定。正しくないなら次へ
    if(ny < 0 || H <= ny || nx < 0 || W <= nx) continue;
    // if(town.at(ny).at(nx) == '#') continue;
    if(checked.at(ny).at(nx)) continue;
    
    // 正しい移動先のny,nxを新しい頂点としてdfs()関数に入力
    if(dfs(std::make_pair(ny, nx))) return true;
  }
  return false;
}

int main() {
  std::cin >> H >> W;
  town.assign(H, std::vector(W, '.'));
  checked.assign(H, std::vector(W, false));
  for(int y = 0; y < H; y++) {
    for(int x = 0; x < W; x++) {
      std::cin >> town.at(y).at(x);
      if(town.at(y).at(x) == '#') checked.at(y).at(x) = true; // 壁を探索済みにすることで関数内の記述を減らす
      if(town.at(y).at(x) == 's') start = std::make_pair(y, x); // start座標のペアを作る
      if(town.at(y).at(x) == 'g') goal = std::make_pair(y, x); // goal座標のペアを作る
    }
  }
  if(dfs(start)) std::cout << "Yes" << std::endl;
  else std::cout << "No" << std::endl;
}

stackバージョン
基本的に同じ構造になるが、再帰を用いた方がコード量は少なくなる。一長一短である。
アルゴリズム的な基本構造としてはスタックである。
スタックを、再帰関数で保持するか、配列で保持するかの違いかなと思う。

#include <iostream>
#include <vector>
#include <stack>

int H, W, max_depth;
std::pair<int, int> start, goal;
std::vector<std::vector<char>> town;
std::vector<std::vector<bool>> checked;
std::stack<std::pair<int, int>> st;

// 次の探索場所への距離を全通り　上　右　下　左　（斜めは移動できない前提があるのでこれで全て）
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

/* Depth First Search : stack version */
bool dfs_stack(std::pair<int, int> start, int result_depth) {
  // 訪問先をtrueにする
  checked.at(start.first).at(start.second) = true;
  st.push(start);
  // スタックが空になるまで
  while(!st.empty()) {
    // スタックの先頭を状態として保持
    std::pair<int, int> state = st.top();
    // スタックの先頭を取り出す
    st.pop();
    // スタックの先頭の状態とゴールが一致すればtrue
    if(state == goal) {
      printf("depth = %d\n", result_depth);
      return true;
    }
    // 深さ
    result_depth++;
    // 深度制限を超えるとfalseを返す
    if(result_depth > max_depth) {
      std::cout << "depth over" << std::endl;
      return false;
    }
    
    for(int i = 0; i < 4; i++) {
      // 移動先を探すため上下左右を判定する
      int ny = state.first + dy[i];
      int nx = state.second + dx[i];
      // 正しい移動か判定。正しくないなら次へ
      if(ny < 0 || H <= ny || nx < 0 || W <= nx) continue;
      // if(town.at(ny).at(nx) == '#') continue;
      if(checked.at(ny).at(nx)) continue;
      // 訪問先をtrue
      checked.at(ny).at(nx) = true;
      // 正しい移動先のny,nxを新しい頂点としてスタックにpush
      st.push(std::make_pair(ny, nx));
    }
  }
  // スタックが空になったらfalse(空になるということはゴールに到達できなかったということ)
  return false;
}

int main() {
  std::cin >> H >> W;
  town.assign(H, std::vector(W, '.'));
  checked.assign(H, std::vector(W, false));
  max_depth = 60; // 深度制限
  for(int y = 0; y < H; y++) {
    for(int x = 0; x < W; x++) {
      std::cin >> town.at(y).at(x);
      if(town.at(y).at(x) == '#') checked.at(y).at(x) = true; // 壁を探索済みにすることで関数内の記述を減らす
      if(town.at(y).at(x) == 's') start = std::make_pair(y, x); // start座標のペアを作る
      if(town.at(y).at(x) == 'g') goal = std::make_pair(y, x); // goal座標のペアを作る
    }
  }
  if(dfs_stack(start, 0)) std::cout << "Yes" << std::endl;
  else std::cout << "No" << std::endl;
}

/*
input

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
###.#.#.#.
#.....#...

output

No
-----------------------------

input

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

output

depth = 52
Yes
*/