POJ_No.2386: Lake Counting

dfs。

/********************************************************************************************
*    2012/04/24                                                                                *
*    プログラミングコンテストちゃれんじブック                                                *
*    p.35 第二章 2-1すべての基本"全探索"                                                        *
*    Lake Conting (POJ NO.2386)                                                                *
*    大きさがN×Mの庭がある。そこに雨が降り、水溜りができた。水溜りは８近傍で隣接している    *
*    場合につながっているとみなす。全部でいくつの水溜りがあるか                                *
*                                                                                            *
*            8近傍***                                                                        *
*                    *w*                                                                        *
*                    ***                                                                        *
*    適当なWからはじめ、そこからつながっている部分を[.]に置き換えるという操作を繰り返す。    *
*    1回のDFSで、はじめのWとつながっているWはすべて[.]に置き換わるため、Wがなくなるまで何回    *
*    DFSを行ったかが答えになる。状態の遷移は8方向の移動の8通りで、DFSは各マスに対してたかだ  *
*    1回しか呼び出されないため、計算量はO(8×N×M)=O(N×M)となる。                            *
*                                                                                            *
*    crane                                                                                *
********************************************************************************************/

/**************************************************
**************!制約!*******************************
***************・N,M≦100**************************
**************************************************/

#include<iostream>

void dfs(int x, int y);    //[w] -> [.]

int N,M;        //縦×横 サイズ
char **field;    //庭

int main(){
    int res=0; //結果

    //庭の大きさ(入力)
    std::cin >>    N >> M;
    /*多次元配列確保*/
    field = new char*[N];
    for(int i=0; i<M; i++){
        field[i] = new char[M];
    }
    //庭作成
    for(int i=0; i<N;i++){
        for(int j=0; j<M; j++){
            std::cin>> field[i][j];
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(field[i][j] == 'W'){
                //Wが残っているならそこからdfsをはじめる
                dfs(i, j);
                res++;
            }
        }
    }
    //結果出力
    std::cout << res << std::endl;
    int ff;
    std::cin >> ff;
    return 0;
}

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

    //移動する8方向をループ
    for(int dx=-1; dx<=1; dx++){
        for(int dy=-1; dy<=1; dy++){
            //x方向にdy y方向にdy移動した場所を(nx,ny)とする
            int nx = x + dx, ny = y + dy;

            //nxとnyが庭の範囲内かどうかとfield[nx][ny]が水溜りかどうかを判定
            if(0 <= nx && ny < N && 0 < ny && ny < M && field[nx][ny] == 'W')    dfs(nx, ny);
        }
    }
}

AOJ Volume0 0067: The Number of Island

dfs.

/****************************************
*    2012/07/03                            *
*    AOJ Volume0 0067                    *
*    The Number of Island                *
*    crane                                *
*****************************************/
#include<iostream>
#include<string>
using namespace std;


int field[12][12];

void dfs(int x, int y);

int main(){
    string input;
    while(getline(cin,input)){
        if(input.empty())
            return 0;
        for(int i=0; i<12; i++){
            for(int j=0; j<12; j++){
                field[i][j] = input[j]-'0';
            }
            getline(cin, input);
        }

        int count = 0;
        for(int i=0; i<12; i++){
            for(int j=0; j<12; j++){
                if(field[i][j] == 1){
                    dfs(j, i);
                    count++;
                }
            }
        }
        cout << count << endl;   
    }
    return 0;
}


void dfs(int x, int y){

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

    field[y][x] = 0;

    for(int i=0; i<4; i++){
        int nx = x + dx[i];    int ny = y + dy[i];
        if(0<=nx && 0<=ny && nx<12 && ny<12 && field[ny][nx]==1)
            dfs(nx, ny);
    }
   
}

AOJ Volume11 1160: How Many Islands

dfsを使用


/********************************************
*   2012/06/18                                *
*    AOJ Volume11 1160                        *
*    How Many Islands?                        *
*********************************************/

//--------------------------------------------------//
//        海->0        陸->1                            //
//--------------------------------------------------//
#include<iostream>

#define MAX_N 50
int field[MAX_N][MAX_N];

/*  w:横  h:縦*/
int w, h;       

void dfs(int x, int y);    //dfs処理用

int main(){
    while(std::cin >> w >> h, w, h){    //地図情報入力
        int result = 0;                 //結果個数初期化
       
        /*地図作成*/
        for(int i=0; i<h; i++)        //縦
            for(int j=0; j<w; j++)    //横
                std::cin >> field[i][j];

        /*島破壊*/
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(field[i][j] == 1){
                    /*島があったら*/
                    dfs(j,i);
                    result++;
                }
            }
        }
        std::cout << result << std::endl;//結果出力
    }
    return 0;
}



void dfs(int x, int y){
    int a[8] = {-1, -1, -1, 0, 1, 1, 1, 0};//横
    int b[8] = {-1,  0,  1, 1, 1, 0,-1,-1};//縦

    //今いるところを0にする
    field[y][x] = 0;

    /* 移動する８近傍をループ*/
    for(int i=0; i<8; i++){
        //移動先 (nx, ny)
        int nx = x + a[i], ny = y + b[i];
       
        //移動先が地図上か判定 & 移動先が島かどうか判定
        if( 0<=nx && nx<w && 0<=ny && ny<h && field[ny][nx]==1)
            dfs(nx, ny);
    }
}

AOJ Volume 0030:Sum of Integers

無駄が多いのでそのうち修正

/******************************************
* 2012/06/29                              *
* AOJ Volume0 0030 Sum of Integers        *
* wrote crane                             *
*******************************************/
#include<iostream>
using namespace std;

int num[] ={ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n=0; //ｎ個の数字
int s=0; //ｎ個の数字の和がsとなる

int count;
void solve(int x, int sum, int c);

int main(){
 while(cin >> n >> s, (n||s)){
  count = 0;
  solve(n, s, 0);
  cout << count << endl;
 }
 return 0;
}

void solve(int x, int sum, int c){//x->ｎ個の数字 ,  sum->和  c->numカウント用
 if(x == 0 && y==0 && c==10){ 
  count++;
  return;
 }else if(9<c || x<0 || y<0){
  return;
 }else{
  int a=y-num[c];
  c++;
  solve(x, y, c); //足さない
  solve(x-1, a,c);//足す
 }
 return;
}