列挙状態POJ 1753-Flip Game(列挙)

2677 ワード

この文章を書く前に、xxxはすでにいくつかの改列挙状態のテーマに関する文章を書いたことがあります.知りたい人は前の文章をめくってもいいです.
     http://poj.org/problem?id=1753
    簡略列挙.
    各格子はひっくり返すかひっくり返さないかの2つの状態しかありません(2回ひっくり返すとひっくり返さないのと同じです).全部で16個の格子で、最大2^16種類の状態しかひっくり返せません.
    Code:
    毎日同じ理屈
青春、笑い声と泣き声が混じる年华があって、青春の少年は青空の中で飞ぶ幼鹰で、完全に成长していませんが、一部の子供っぽくて、一部の愚かで、両亲の両手を脱ぐことができなくて、自分の空を探して、一时の情热のためで、1种の一人で飞ぶ感じです!
#include <stdio.h>



bool s[20][20];

int best;



int check()

{

    int i, j, tot = 0;

    for(i=0;i<4;i++) for(j=0;j<4;j++) tot +=s[i][j];

    if(tot == 0 || tot == 16) return 1;

    return 0;

}

void Echange(int x, int y)

{

    s[x][y] = !s[x][y];

    s[x+1][y] = !s[x+1][y];

    s[x][y+1] = !s[x][y+1];

    if(x>0) s[x-1][y] = !s[x-1][y];

    if(y>0) s[x][y-1] = !s[x][y-1];



}

void Search(int k, int ans)

{

    int x, y;

    if(16 == k) {

        if( check()&& ans <best) best = ans;

    }else {

        x = k /4;

        y = k %4;

        Search(k+1,ans);//  

        Echange(x, y);

        Search(k+1,ans+1);// 

        Echange(x, y);

    }

}

void work()

{

    int i, j;

    char c;

    for(i = 0; i<4; i++)

    {

        for(j = 0; j<4; j++){

            scanf("%c", &c);

            if(c=='w') s[i][j] = 0;

            else s[i][j] = 1;

        }

        getchar();

    }

    //for(i=0;i<4;i++){for(j=0;j<4;j++) printf("%d",s[i][j]);printf("
");} best = 1000; Search(0, 0); for(i=0;i<4;i++) for(j=0;j<4;j++) s[i][j] =!s[i][j]; Search(0, 0); if(best != 1000) printf("%d
",best); else printf("Impossible
"); } int main() { work(); return 0; }

    参照リンク:
     http://blog.csdn.net/lyy289065406/article/details/6642595
ある日、一人の男が森を通り抜けたとき、小さな声で彼を呼んだ.彼は頭を下げて見るとカエルだった.「キスしてくれれば、きれいなお姫様になるよ」男は一言も言わずにカエルを拾い、ポケットに入れた.「キスしてくれれば、私は美しいお姫様になるよ.そして、出会ったすべての人に、あなたはどんなに頭が良くて勇敢なのか、あなたは私の英雄なのか教えてくれるよ」男はカエルを出して、それに向かってかすかに笑って、またポケットに戻した.「キスしてくれれば、私は美しいお姫様になります.それから、私はあなたの妻になりたいです.」男はまたカエルを出して、それに向かってかすかに笑って、ポケットに戻しました.「キスしてくれれば、私は美しいお姫様になります.それから、私はあなたの妻になりたいです.そして、あなたは私に何でもすることができます.」もう一度、男はカエルを出して、それに向かってかすかに笑って、ポケットに戻しました.最后に、カエルは力がなくて闻きます:“私はこんなに良い条件を出して、どうしてあなたはまだ私にキスしませんか?”男の人は言います:“私はプログラマーで、私はどんな王女とごろつきをする时間がありません.しかし、1つの话すことができるカエルを持って、とてもクールです.”
--------------------------------------オリジナル記事By列挙とステータス-------------------------------