DFS/BFS 備忘録

DFS/BFSの練習備忘録
[参考]
https://qiita.com/drken/items/996d80bcae64649a6580
https://qiita.com/drken/items/6a95b57d2e374a3d3292

【12/23更新】
M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)　D

https://atcoder.jp/contests/abc232/tasks/abc232_d

迷路探索で一番深いところの位置を出す問題。
DFSっぽいなと思ったので、再起のDFSで解いてみた。
C[h][w]に地図を入力、スタートは(0,0)として、再起DFS。
終端部の判定のため、Cは定義域の外側は壁（#）にしておく。
x+1 or y+1が空きなら進める条件にしてDFSで再起していく。
cntで深度ｶｳﾝﾀを用意しておき、進んだらcnt++する。
x+1, y+1がそれぞれ壁（#）もしくは、訪問済みの場合はそこが終端なので、
ansをcntで更新。
で、ここから戻ることになるので、cnt--にして次の探索になる。
進んだらcnt++, 戻ったらcnt--って感じのイメージで作った。
再起関数はｲﾏｲﾁ理解進まなかったが、これは比較的わかりやすいと思った。

```php
#include <stdio.h>
#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//cout << fixed << setprecision(15);    
ll mod=1e9+7;
char C[110][110];
vector<vector<bool>>seen(110);
queue<pair<int,int>>q;
set<pair<int,int>>vis;
ll h,w;
ll cnt=0;
ll ans=0;

void dfs(char A[110][110],ll y, ll x){
    seen[y][x]=true;
    cnt++;

    if(C[y][x+1]=='.' && x+1!=w){
        if(seen[y][x+1]==0){
            dfs(C,y,x+1);
        }
    }
    if(C[y+1][x]=='.' && y+1!=h){
        if(seen[y+1][x]==0){
            dfs(C,y+1,x);
        }
    }
    if ((C[y][x+1]=='#' || seen[y][x+1]==1) && (C[y+1][x]=='#'||seen[y+1][x]==1)){
        ans=max(ans,cnt);
        cnt--;
    }
}

int main(void){
    cin>>h>>w;
    rep(i,0,110){
        rep(j,0,110){
            C[i][j]='#';
            seen[i].push_back(false);
        }
    }
    rep(i,0,h){
        string t;
        cin>>t;
        rep(j,0,w){
            C[i][j]=t[j];
        }
    }
    dfs(C,0,0);
    cout<<ans<<endl;

}

```



https://atcoder.jp/contests/abc204/tasks/abc204_c
動的計画法の幅優先探索を用いる問題。

[グラフ入力]
・動的配列 ```vector<vector<int>>```で、各点から訪問できるところを入力する。

[探索]
・探索待ち配列（q:queue配列）と訪問済み配列(vis：set配列)を用意する。
・ある点をスタート地点として選ぶ
・スタート地点を探索待ち、訪問済み配列に入力する。
・探索待ち配列から探索待ちの値を取り出す。
・探索待ち配列から取り出した値を消す。
　　※最初に入力した値を取出し、消去するのがが幅優先探索、
最後に入力した値を取り出すのが深さ優先探索
・探索待ちから取り出した値から、訪問できるところを先の動的配列から取り出す。
・取り出した訪問できるところが、訪問済みかどうかを判定
・未訪問の場合は、探索待ちに追加、訪問済みに追加する
・探索待ちに追加されたものがある場合は、Whileで探索待ちがなくなるまで繰り返す
※訪問できるところがなくなったら探索待ちに追加されなくなるので終了する。
・いくつ訪問できたかを出力し、ansに加算する。
・次の地点をスタート地点にして、再度上記探索を繰り返す。

この流れがいわゆる幅優先探索。
これは知識として知らないとまず実装できない類。
とにかく数こなして慣れていくしかないタイプのやつ。


```php
#include <bits/stdc++.h>
#include <math.h>
using namespace std;

int main(){
	int N,M;
	cin >> N >> M;
    vector<vector<int>>G(3000);//グラフ用

	for(int i=0;i<M;i++){//グラフ入力
		int a,b;
		cin >> a >> b;  
		G[a].push_back(b);
	}
    int ans=0;
    for(int i=1;i<=N;i++){//スタート地点を全探索
        queue<int>q;//探索待ち用
        set<int>vis;//訪問した記録用
        q.push(i);//まずスタート地点をキューに入れる
        vis.insert(i);//スタート地点を訪問済みに入れる

    while(q.empty()==0){//探索待ちになんかある限りループ
        int A =q.front();//探索待ちの先頭を取り出す
        q.pop();//キューの先頭を消す
        for(auto j:G[A]){//Aからいけるところを全出力する
            if(vis.count(j)==0){//未訪問の場合だけ。
                q.push(j);//探索待ちに追加
                vis.insert(j);//訪問済みに追加
            }
            //未訪問あったらqが加算されるので、whileﾙｰﾌﾟ継続
            //訪問済みの場合はqが加算されないので、qが空になってループ解除
        }
    }
        ans=ans+vis.size();//i地点からいける数をansに足す
    }
	cout << ans<<endl;;
}
```

https://atcoder.jp/contests/abc007/tasks/abc007_3
ABC007_C
典型的な迷路探索問題。
始点と終点が与えられて、最短距離を求める問題。

ABC204_Cの学習後に取り組み、8割がた自分の力で書けた。
考え方は同じで行けるが、座標に対してqueueとsetの処理が必要。
これを```pair```でやっていくところに気づけたら、あとは時間かかったけどやれた。
4方向の記述がスマートじゃない気がするが、気にせず幅優先探索で実装。
各点の距離を```dis[y][x]```で格納し、```dis[gy][gx]```が求める答えになる。
ちなみに```vis.size()```で始点からたどり着ける全点の数が出力される。


```php
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
    int R,C,sy,sx,gx,gy;
    char c[60][60];
    cin>>C>>R>>sy>>sx>>gy>>gx;
    for(int i=1;i<=C;i++){
        for(int j=1;j<=R;j++){
            cin>>c[i][j];
        }
    }

    int dis[60][60];
    dis[sy][sx]=0;
    queue<pair<int,int>>q;
    set<pair<int,int>>vis;
    q.push(make_pair(sy,sx));
    vis.insert(make_pair(sy,sx));

    while(q.empty()==0){
        pair<int,int>curr=q.front();
        int y=curr.first;
        int x=curr.second;
    //    cout<<"y:"<<y<<" x:"<<x<<endl;
        q.pop();
        if(y==gy && x==gx){
            break;
        }
        else{
            if(c[y][x+1]=='.'){
                pair<int,int>next={y,x+1};
                if(vis.count(next)==0){
                    q.push(make_pair(y,x+1));
                    vis.insert(make_pair(y,x+1));
                    dis[y][x+1]=dis[y][x]+1;
                }
            }
            if(c[y][x-1]=='.'){
                pair<int,int>next={y,x-1};
                if(vis.count(next)==0){
                    q.push(make_pair(y,x-1));
                    vis.insert(make_pair(y,x-1));
                    dis[y][x-1]=dis[y][x]+1;
                }       
            }
            if(c[y+1][x]=='.'){
                pair<int,int>next={y+1,x};
                if(vis.count(next)==0){
                    q.push(make_pair(y+1,x));
                    vis.insert(make_pair(y+1,x));  
                    dis[y+1][x]=dis[y][x]+1;      
                }
            }
            if(c[y-1][x]=='.'){
                pair<int,int>next={y-1,x};
                if(vis.count(next)==0){
                    q.push(make_pair(y-1,x));
                    vis.insert(make_pair(y-1,x));     
                    dis[y-1][x]=dis[y][x]+1;   
                }
            }            
        }
    }
    cout<<dis[gy][gx]<<endl;
}
```