あるごりの復習。〜〇〇優先〜
何もなければ１日に１問。時に２問
まぁ知っていないと困りそうだんぁ〜っていう焦りからですね。
なんとなく、デイリーなワークとしてはじめて見るよ。
ちなみに、ブルゾンの”dirty work”を”daily work”と思っている人がいるらしい。
MV見れば全く”daily”じゃないのに。。。
んで、この本をやってみるのはいいけど、続くかなぁ。基礎的な部分だけでも得られればいいんだよね１区切りついた段階でアップしていく、スタイル？多分。
あと、多分めちゃくちゃフランクに進めていくし、若干本家と違うかもだけど、
あくまで自分が理解できていればいいスタンスなので！
ぶっちゃけ、遊びたい
まぁ遊ぶけど、一人酒に慣れてきて、、、まだ学生だぜ。。。
それでは、
DFS(depth first search)
深さ優先探索ってやつ。昔やった。
要は、あるポイントを見つける。
その状態から繊維できなくなる状態までいってみる
限界迎えたら、１つ前に戻ってみる。
ってことを繰り返して探索するんだけど、つまり再帰関数が得意とする探索で。暗に、スタック(先入れ後出し)を意味しているらしい。へぇ。
計算量O(2^N)。メモリ使用量は再帰関数の深さに比例する。（深く潜る分だけ、浅いところを待たせている。）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
//部分話をとく問題 //整数a1~an がgiven (n個) //いくつか選んで、合計kにできるか #include <cstdio> int a[7] = {1,5,8,3,6,4,3} ; int n = 3; int k = 7; //深さ優先木を作る //i : 深さ(配列長とみなせる),sum : //n : 最大深度 bool dfs(int i, int sum){ //最大深度に到達したら、その地点での合計とkを比較 if(i == n) return sum == k; //**最大深度でない場合に次の深度へ //深度iを使う場合に分岐(分岐先でtrueならこれもtrue,そうでないなら<*>) if(dfs(i+1,sum)) return true; //深度iを使わない場合に分岐(分岐先でtrueならこれもtrue,そうでないなら<*>) if(dfs(i+1,sum+a[i])) return true; //<*>そうでない場合 return false; } void solve(){ if (dfs(0,0)) printf("Yes\n"); else printf("No\n"); } int main(){ solve(); } |
んで、もう一個あった。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
//大きさN*Mの庭にの中に水たまりを設定 //8近傍に水たまりがあれば、連結とみなし //何個水たまりが存在するか？ #include <stdio.h> #include <time.h> #include <stdlib.h> //庭の大きさ const int N = 10; const int M = 10; char field[N][M]; //水たまりのランダム作成 void set_input(){ const char str[] = "W."; //水：w、土：. srand((unsigned int)time(NULL)); for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ field[i][j] = str[rand()%2]; printf("%c",field[i][j]); } printf("\n"); } printf("\n"); return; } //現在状況出力 void out_put(){ for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ printf("%c",field[i][j]); } printf("\n"); } printf("\n"); return; } //深さ優先木２ //あるポイント(i,j)から手繰れるポイントまで到達してみる。 void dfs(int i,int j){ //水を土にしていく（到達ポイントは目印として、”.”にする） field[i][j] = '.'; //(i,j)から８方向に深掘りする for(int tmp_i = i-1; tmp_i <= i + 1; tmp_i++){ for(int tmp_j = j-1; tmp_j <= j + 1; tmp_j++){ //庭の範囲内確認 if(tmp_j >= 0 && tmp_j >= 0 && tmp_i <= N && tmp_j <= M){ if(field[tmp_i][tmp_j] == 'W'){ //さらに手繰れる場合は次の深度へ dfs( tmp_i , tmp_j ); } } } } return; } //深さ優先木１ //深さ：座標になる。 void solve(){ int ans = 0; for(int n = 0; n < N; n++){ for(int m = 0; m < M; m++){ //水ポイントを発見 if(field[n][m] == 'W'){ ans++; dfs(n,m); //そこからできる範囲で土にしていく(深さ優先) out_put(); //次なる水ポイントを発見する。 } } } printf("%d\n",ans); return; } int main(){ set_input(); solve(); } |
今日はここまでだわ。疲れた。