AOJ Volume11 1129: Hanafuda Shuffle (POJ1978)

問題文通りにそのまま書いてみた。


/********************************
*    2012/0623                    *
*   AOJ VOlume11 1129           *
*    POJ1978                     *
*   花札シャッフル              *
*    crane                       *
********************************/

#include<iostream>

#define MAX_N 50
int card[MAX_N];    //カード内容
int t_card[MAX_N];    //シャッフル用カードtmp

int main(){

    int n = 0;    //札の枚数
    int r = 0;    //カット回数
    int p = 0;    //p枚目から
    int c = 0;    //c枚取り出す

    while(std::cin >> n >> r, n, r){
        //配列の初期化
        for(int i=0; i<n; i++)        card[i] = i + 1;
       
        //shuffle
        for(int i=0; i<r; i++){    //カット回数r分
            std::cin >> p >> c;

            for(int j=0; j<c; j++)
                t_card[c-1-j] = card[n-p-j];

            for(int j=n-p+1; j<n; j++)
                card[j-c] = card[j];

            for(int j=0; j<c; j++)
                card[n-c+j] = t_card[j];
        }

        std::cout << card[n-1] << std::endl;

    }
    return 0;
}

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);
        }
    }
}