深さ優先探索 - ないものは作りましょう。

蟻本で深さ優先探索を読んだので、kyuridenamidaさんのブログでまとめられていた問題を解いてみました。
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏

AOJ Volume0 0030 Sum Of Integers

#include <stdio.h>

int ans=0;
int s;

void dfs(int n, int a, int sum) {
    if(a==0 && sum==s) {ans++;return;}
    if(n==10) return;
    dfs(n+1, a-1, sum+n);  // nを使う
    dfs(n+1, a, sum);  // nを使わない
    return;
}

int main(){
    for(;;) {
        int a;
        ans=0;
        scanf("%d %d",&a,&s);
        if(a==0 && s==0) break;
        dfs(0, a ,0);
        printf("%d\n",ans);
    }
    return 0;
}

AOJ Volume0 0033 玉

玉 | Aizu Online Judge

#include <stdio.h>

int ball[10];

bool dfs(int n, int b, int c) {
    if(n==9) {
        if(ball[n] > b || ball[n] > c) return true;
        else return false;
    }
    if(ball[n] > b && dfs(n+1,ball[n], c)) return true;
    if(ball[n] > c && dfs(n+1,b, ball[n])) return true;
    return false;
}

int main(){
    int n;scanf("%d",&n);
    for(int l=0;l<n;l++) {
        for(int i=0;i<10;i++) scanf("%d",&ball[i]);
        if(dfs(0,0,0))printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

AOJ Volume0 0067 The Number of Island

島の数 | Aizu Online Judge

#include <stdio.h>

char island[12][15];

int dirx[4] = {0,1,0,-1};
int diry[4] = {-1,0,1,0};

void dfs(int x, int y) {
    if(x<0 || y<0 || x>=12 || y>=12) return;
    island[y][x]='0';
    for(int i=0;i<4;i++) {
        int nx=x+dirx[i];
        int ny=y+diry[i];
        if(island[ny][nx]=='1') dfs(nx,ny);
    }
    return;
}

int main(){
    while(true) {
        for(int i=0;i<12;i++) if(scanf(" %s",island[i])==EOF) return 0;
        int ans = 0;
        for(int i=0;i<12;i++)
            for(int j=0;j<12;j++)
                if(island[i][j] == '1') {
                    dfs(j,i);
                    ans++;
                }
        printf("%d\n",ans);
    }
    return 0;
}

AOJ Volume2 0207 Block

Block | Aizu Online Judge

#include <stdio.h>
#include <vector>
using namespace std;

int w,h;
int bd[100][100];
int xs,ys;
int xg,yg;
int sc;

const int dirx[4] = {0,1,0,-1};
const int diry[4] = {-1,0,1,0};

bool dfs(int x, int y) {
    if(x==xg && y==yg) return true;
    bd[y][x]=-2;
    for(int i=0;i<4;i++) {
        int nx=x+dirx[i],ny=y+diry[i];
        if(nx<0 || ny<0 || nx>=w || ny>=h) continue;
        if(bd[ny][nx]!=sc) continue;
        if(dfs(nx,ny)==true) return true;
    }
    return false;
}

int main() {
    while(1) {
        scanf("%d %d",&w, &h);
        if(w==0 && h==0) break;
        for(int y=0;y<100;y++)for(int x=0;x<100;x++) bd[y][x]=-1;
        scanf("%d %d",&xs,&ys);
        scanf("%d %d",&xg,&yg);
        xs--;ys--;xg--;yg--;
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++) {
            int c,d,x,y;
            scanf("%d %d %d %d",&c,&d, &x, &y);
            x--;y--;
            if(d)
                for(int py=0;py<4;py++)
                    for(int px=0;px<2;px++)
                        bd[y+py][x+px] = c;
            else
                for(int py=0;py<2;py++)
                    for(int px=0;px<4;px++)
                        bd[y+py][x+px] = c;
        }
        sc = bd[ys][xs];
        if (dfs(xs,ys) == true) printf("OK\n");
        else printf("NG\n");
    }
    return 0;
}

AOJ Volume1 0118 Property Distribution

Property Distribution | Aizu Online Judge

#include <stdio.h>
#include <vector>
using namespace std;

int h,w;
int bd[100][100];
int tgt;

int dirx[4]={0,1,0,-1};
int diry[4]={-1,0,1,0};

void dfs(int x,int y) {
    bd[y][x]=-1;
    for(int i=0;i<4;i++) {
        int nx=x+dirx[i], ny=y+diry[i];
        if(nx<0 || ny<0 || nx>=w || ny>=h) continue;
        if(bd[ny][nx]!=tgt) continue;
        dfs(nx,ny);
    }
    return;
}

int main() {
    while(1) {

    scanf("%d %d",&h,&w);
    if(h==0 && w==0) break;
    for(int y=0;y<h;y++) {
        char str[102];
        scanf("%s",str);
        for(int x=0;x<w;x++) {
            if(str[x] == '@') bd[y][x] = 1;
            if(str[x] == '#') bd[y][x] = 2;
            if(str[x] == '*') bd[y][x] = 3;
        }
    }

    int ans=0;
    for(int y=0;y<h;y++) {
        for(int x=0;x<w;x++) {
            if(bd[y][x]!=-1) {
                tgt=bd[y][x];
                dfs(x,y);
                ans++;
            }
        }
    }
    printf("%d\n",ans);

    }
    return 0;
}