2₋1　全探索

全探索とはすべての可能性を調べ、その中から解を探す方法である。

再起関数

関数の中で同じ関数をまた呼ぶ関数である。有名な例としてFACTORIALとフィボナッチ数列がある。

フィボナッチ数列

wikiの説明
https://g.co/kgs/KDZc9E

簡単な概要

フィボナッチ数列とはNに対する解を返すためn-1とn-2を足した結果を返す。
コードではnに対する解がないためnが０になるでfib(n-1)+fib(n-2)を繰り返してif(n <= 1){return n;}で０になってreturnされる解を全部持ってくる。

コード

#include <iostream>
//std省略
using namespace std;

const int MAX_N = 100;
int memo[MAX_N+1];
int fib(int n){
  if(n <= 1){return n;} 
  //メモがあれが再帰する前にメモ参照
  if(memo[n] != 0){return memo[n];}
  //再帰
  return memo[n] = fib(n-1)+fib(n-2);
}
int main(){
    int g;
    cin >> g;
    cout << fib(g);
}

コードではメモ化を適用している。メモをしなければfib(4)で13が出るためには8が出るためのfib(n-1)+fib(n-2)の繰り返しと５が出るためのfib(n-1)+fib(n-2)の繰り返しが行われ、いらない計算が増えてしまう。メモがあれが再帰する前にメモ参照し、再帰せずに済む。

スタック

簡単な概要
wikiの説明
https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF

ポイント　

LIFO
最後に入ったものが一番早く出る。
Push Pop
入れる　出す

コード

#include <stack>
#include <iostream>
using namespace std;

int main(){
    stack<int> s;
    s.push(1);
    for(int a=1;a<4;a++){
        s.push(a);
    }
    //s={1,1,2,3}
    for(int a=1;a<4;a++){
    //一番上の値を表示する
        cout << s.top() << endl;
        s.pop();
    //s={1}
    }
}

キュー

簡単な概要
wikiの説明
https://ja.wikipedia.org/wiki/%E3%82%AD%E3%83%A5%E3%83%BC_(%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF)

ポイント　

FIFO
最初に入ったものが一番早く出る。
Enqueue Dequeue
入れる　 出す

コード

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
int main() {
  queue<int> s;
  
    s.push(1);
    for(int a=1;a<4;a++){
        s.push(a);
    }
    //s = {3,2,1}
    cout<<"front: " << s.front()<<" back: "<< s.back() << endl;
    for(int a=1;a<4;a++){
        s.pop();
        cout<<"front: " << s.front()<<" back: " << s.back() << endl;
    }
    //s = {3}
    if(s.empty()){cout << "s.empty() = true\n";}
    else{cout << "s.empty() = false\n";}
    cout<<"s.size() = "<<s.size();

}

実行結果

front: 1 back: 3
front: 1 back: 3
front: 2 back: 3
front: 3 back: 3
s.empty() = false
s.size() = 1

深さ優先探索 DFS

簡単な概要
左から一番奥を探索してその後、右の奥も探索する

https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

問題1

部分和問題

整数がn個指定され、整数の和がｋなるか判定する。

コード

//部分和問題
#include <cstdio>
#include <iostream>
using namespace std;

const int MAX_N = 20;
int a[MAX_N]={1,2,4,7},n,k;//nは整数の個数　ｋは和
// iまででsumを作って,残り以降を調べる
bool dfs(int i,int sum) {
    //枝刈り
    if(i>n) return false;
    //n個決め終わったら、今までの和sumがkと等しいかを返す
    if(i==n) return sum == k;
    //下の二つのコードは1,2,4,7をsumに追加するかしないかのDFS
    //a[i]を使わない場合
    if(dfs(i +1,sum)) return true;
    //a[i]を使う場合
    if (dfs(i+1,sum+a[i]))return true;
    //a[i]を使う使わないに拘わらずkが作れないのでfalseを返す
    return false;
}
void solve(int a,int b){
    if (dfs(a,b)) cout << "yes\n";
    else cout << "NO\n";
}
int main(){
  /*
    cin >> n; 
    
    for(int i =0;i<n;i++){
        int ai;
        cin >> ai;
        a[i] = ai;
    }
   
    cin >> k;
  */
  n=4;
  k=13;
  solve(0,0);
}

実行結果

yes

説明

コードでは再帰が実行される。
iが段々増えて指定したnになった場合、sumの値がkと等しいかを返す。

if(i==n) return sum == k;

trueが変えされた場合に

    if(dfs(i +1,sum)) return true;
    if (dfs(i+1,sum+a[i]))return true;

再帰が終わり、solve(0,0);に対してのtrueをかえすことができる。
true出ない場合は

//枝刈り
    if(i>n) return false;

aに無数のデータが入っている仮定では指定したiがnより多く探索し続けるこどで
再帰が終わらないため上の条件を入れて再帰を終了させる。

問題2 POJ No.2386

Lake Counting

N*Xのサイズの庭があり。そこに雨が降って水たまりができた。水の8近傍にまた水がある場合、同じ水たまりの部分として認識する。
N*Xのサイズの庭にはいくつの水たまりがあるのだろうか。

入力例

//10 12
//W........WW.
//.WWW.....WWW
//....WW...WW.
//.........WW.
//.........W..
//..W......W..
//.W.W.....WW.
//W.W.W.....W.
//.W.W......W.
//..W.......W.

流れ
０．今の座標で水があればその座標を点に変える
１．8近傍に水があるか探索、あれば見つけた座標で0を実行、なければカウントに追加する。
２．1で水がなければ、ｘ座標を移す
３．ｘ座標が終わったらｙ座標も移す
４．0123を全ての座標の探索が終わるまで繰り返す
０と1は水たまりが消されるまで繰り返す

コード

//lake counting
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int N,M;

const int MAX = 100;
char field[MAX][MAX+1]={

};
void dfs(int x,int y){
    //今いるところを．に置き換える
    field[x][y] = '.';

    //移動する8方向をループ
    //0　3　5
    //1　.　6 　点はx,yの座標　
    //2　4　7
    //上の順番でループを行う
    for(int dx= -1;dx <= 1; dx++){
        for(int dy = -1; dy<= 1; dy++){
            //x方向にdx y方向にdy 移動した場所を(nx,ny)とする
            int nx = x+dx, ny = y+dy;
			
            //nxとnyが庭の範囲内かどうかとfield[nx][ny]が水たまりかどうかを判定
            if(0<= nx && nx< N && 0<= ny && ny < M &&field[nx][ny] == 'W') dfs(nx,ny);
            //0 <= nx && nx < N x座標の8近傍の探索で指定した範囲を出ていないか判定
            //0 <= ny && ny < M y座標の8近傍の探索で指定した範囲を出ていないか判定
            //field[nx][ny] == 'W' 上の条件がTUREでその点がWであればdfsをまた行う
            //dfs(nx,ny)でその点が.になっり、結果的に8近傍が.になるまで繰り返される。
        }
    }
    return ;
}

void solve(){
    int res = 0;
    for(int i =0; i< N; i++){
        for(int j=0;j<M;j++){
            if(field[i][j]=='W'){
            	//Wがあるならばdfsを始める
                //Wが残っているならそこからdfsを始める
                dfs(i,j);
                res++;
//res = 1
//.........WW.
//.........WWW
//.........WW.
//.........WW.
//.........W..
//..W......W..
//.W.W.....WW.
//W.W.W.....W.
//.W.W......W.
//..W.......W.

//res = 2
//............
//............
//............
//............
//............
//..W.........
//.W.W........
//W.W.W.......
//.W.W........
//..W.........

//res = 3
//............
//............
//............
//............
//............
//............
//............
//............
//............
//............
            }
        }
    }
    cout << res;
}

int main(){
    cin >> N >> M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            cin >> field[i][j];
        }
    }
    //resが表示される
    solve();
}