Atcoder解いてみた　AtCoder Typical Contest A - 深さ優先探索

# AtCoder Typical Contest A - 深さ優先探索
問題は[こちら](https://atcoder.jp/contests/atc001/tasks/dfs_a)  

# 回答
## 深さ優先探索
```C++
#include <iostream>
#include <string>
#include <map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

struct Indice {
    int x;
    int y;
};

bool dfs(const vector<string>& town, vector<vector<bool>>& seen, const int H, const int W, const Indice& sIndice) {
    seen[sIndice.y][sIndice.x] = true; // 訪問済み

    //上下左右の隣接点を探索
    for (int i = 0; i < 4; i++) {

        Indice nextIndice{ sIndice.x + dx[i] , sIndice.y + dy[i] };

        // 隣接点は街からはみ出さないかつ、塀じゃない
        if (0 <= nextIndice.x && nextIndice.x < W && 0 <= nextIndice.y && nextIndice.y < H && town[nextIndice.y][nextIndice.x] != '#') {
            if (seen[nextIndice.y][nextIndice.x]) continue; // 隣接点が探索済みの場合、スルー

            if (town[nextIndice.y][nextIndice.x] == 'g') {
                return true; // ゴールにたどり着いたら終了
            };

            if(dfs(town, seen, H, W, nextIndice)) return true; // 深く探索していきゴールにたどり着いたら終了
        }
    }

    return false;
}

int main() {
    int H;
    int W;
    vector<string> town;
    town.resize(500); // 高さを500に

    vector<vector<bool>> seen;
    seen.resize(500);

    cin >> H >> W;

    // H-1, W-1をはみ出せない
    for (int i = 0; i < H; i++) {
        cin >> town[i];
        seen[i].resize(500);
    }

    // 深さ優先探索で、sからgへたどり着けるか
    // .は道だが、#は塀

    // スタート、ゴールの座標を取得(後者はいらないかも)
    // スタートから深さ優先探索で探索していき、ゴールにたどり着けるか
    // ゴールにたどり着けない条件→深さ優先探索終わってもゴールフラグがtrueにならない

    // スタートの座標を取得
    Indice sIndice;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < town[i].size(); j++) {
            if (town[i][j] == 's') {
                sIndice.x = j;
                sIndice.y = i;
            }
        }
    }

    // スタート地点から深さ優先探索
    bool isReach = false;
    isReach = dfs(town, seen, H, W, sIndice);

    if (isReach) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}
```

## 幅優先探索
```C++
#include <iostream>
#include <string>
#include <map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

struct Indice {
    int x;
    int y;
};

int main() {
    int H;
    int W;
    vector<string> town;
    town.resize(500); // 高さを500に

    vector<vector<bool>> seen;
    seen.resize(500);

    cin >> H >> W;

    // H-1, W-1をはみ出せない
    for (int i = 0; i < H; i++) {
        cin >> town[i];
        seen[i].resize(500);
    }

    // 深さ優先探索で、sからgへたどり着けるか
    // .は道だが、#は塀

    // スタート、ゴールの座標を取得(後者はいらないかも)
    // スタートから幅優先探索で探索していき、ゴールにたどり着けるか
    // ゴールにたどり着けない条件→幅優先探索終わってもゴールフラグがtrueにならない

    // スタートの座標を取得
    Indice sIndice;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < town[i].size(); j++) {
            if (town[i][j] == 's') {
                sIndice.x = j;
                sIndice.y = i;
            }
        }
    }

    // スタート地点から深さ優先探索
    bool isReach = false;

    queue<Indice> que;
    seen[sIndice.y][sIndice.x] = true; // スタート地点は訪問済み

    que.push(sIndice); // スタート地点をキューに

    // 幅優先探索
    while (!que.empty()) {
        Indice uIndice = que.front();
        que.pop();

        // 上下左右の隣接点を探索
        for (int i = 0; i < 4; i++) {
            Indice vIndice{ uIndice.x + dx[i], uIndice.y + dy[i] };
            // 隣接点は街からはみ出さないかつ、塀じゃないかつ、未訪問
            if (0 <= vIndice.x && vIndice.x < W && 0 <= vIndice.y && vIndice.y < H && town[vIndice.y][vIndice.x] != '#' && !seen[vIndice.y][vIndice.x]) {
                que.push(vIndice);
                seen[vIndice.y][vIndice.x] = true; // 訪問済みにする

                if (town[vIndice.y][vIndice.x] == 'g') isReach = true;
            }
        }
    }

    if (isReach) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}
```