A - 深さ優先探索

コメント歓迎です。
問題名の通り、今回から深さ優先探索にチャレンジします。

再帰関数の動きに慣れるまで苦戦しました。

問題

AtCoder 版！蟻本 (初級編) - Qiita より

atc001.contest.atcoder.jp

方針

この問題では、深さ優先探索ができる再帰関数を作ることさえできれば、解答できると思います。
しかし、最初はそこに苦戦するわけです。

どうやってGOALを探していくかについては、AtCoderのchokudaiさんのスライドが参考になります。
(問題ページにある解説と同じものです。)

深さ優先探索による塗りつぶし from AtCoder Inc.

www.slideshare.net

今回は再帰関数のイメージがない人に向けて書いてみようと思います。

再帰関数とは、関数の処理の中で自分自身を呼び出し再帰的な動作をする関数です。
マトリョーシカ的なイメージです。

自分自身を呼び出しているので永遠に処理が終わらないのではと思われるかもしれませんが、
関数の処理の中にif文など条件を付けることで呼び出しを終えられます。

今回私が書いた関数dfs(Depth First Search)はtrueかfalseを戻り値とします。

条件により、最後に呼び出した関数dfsの戻り値が決まると芋づる式に今までに呼び出した関数dfsの戻り値も決まっていきます。

大きなものから順番に開けたマトリョーシカを、今度は小さいものから元に戻していくイメージです。

最初に呼び出した関数dfsの戻り値がGOALにたどり着けたかの答えになります。

イメージが掴めたら考えてみてほしいのですが、ちなみに芋づる式という表現は正確ではありません。

道が2つに分岐したときをマトリョーシカで言い換えるならば、開けたら小さいマトリョーシカが2個入っているということになるからです。

流れ的には片方のマトリョーシカを開けきった後、戻し始めて2つ入っている元の状態に戻ったらもう片方を開け始める感じです。

ちょっとマトリョーシカの例が良くなかった気がしますが理解の助けになれば幸いです。

処理の詳細はコード中のコメントに記載しましたので、それを参照してください。

コード(AC)

#include <iostream>
using namespace std;

// 変数定義 
int H, W;
string c[500]; // 最大500行
 
const int dh[] = {1, -1, 0, 0};
const int dw[] = {0, 0, 1, -1};

int count = 0;

// 深さ優先探索
bool dfs(int h, int w) {
  // goalを見つけたらtrueを返す
  if (c[h][w] == 'g') return true;
  // 一度通った場所は'#'に置き換えてしまう
  c[h][w] = '#';
  // 上下左右1つずつ移動
  for (int i = 0; i < 4; i++) {
    int nh = h + dh[i]; // 移動先のh座標
    int nw = w + dw[i]; // 移動先のw座標
    // 進んだ先が街からはみ出してたら処理をスキップ
    if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
    // 進んだ先が塀だったら処理をスキップ
    if (c[nh][nw] == '#') continue;
    // goalまでたどり着いた場合、呼び出したすべて関数dfsがtrueを返す
    if (dfs(nh, nw)) return true;
  }
  // goalまでたどり着けなかった場合は呼び出した全ての関数dfsがfalseを返す
  return false;
}
 
int main() {
  // 入力
  cin >> H >> W;
  for (int i = 0; i < H; i++) {
    cin >> c[i];
  }

  // goalにたどり着けたか判定する変数
  bool judge;

  // start地点を探して深さ優先探索を開始
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (c[i][j] == 's') judge = dfs(i, j);
    }
  }

  // 出力
	cout << (judge ? "Yes" : "No") << endl;
	return 0;
}