列挙状態POJ 1753-Flip Game(列挙)
2677 ワード
この文章を書く前に、xxxはすでにいくつかの改列挙状態のテーマに関する文章を書いたことがあります.知りたい人は前の文章をめくってもいいです.
http://poj.org/problem?id=1753
簡略列挙.
各格子はひっくり返すかひっくり返さないかの2つの状態しかありません(2回ひっくり返すとひっくり返さないのと同じです).全部で16個の格子で、最大2^16種類の状態しかひっくり返せません.
Code:
毎日同じ理屈
青春、笑い声と泣き声が混じる年华があって、青春の少年は青空の中で飞ぶ幼鹰で、完全に成长していませんが、一部の子供っぽくて、一部の愚かで、両亲の両手を脱ぐことができなくて、自分の空を探して、一时の情热のためで、1种の一人で飞ぶ感じです!
参照リンク:
http://blog.csdn.net/lyy289065406/article/details/6642595
ある日、一人の男が森を通り抜けたとき、小さな声で彼を呼んだ.彼は頭を下げて見るとカエルだった.「キスしてくれれば、きれいなお姫様になるよ」男は一言も言わずにカエルを拾い、ポケットに入れた.「キスしてくれれば、私は美しいお姫様になるよ.そして、出会ったすべての人に、あなたはどんなに頭が良くて勇敢なのか、あなたは私の英雄なのか教えてくれるよ」男はカエルを出して、それに向かってかすかに笑って、またポケットに戻した.「キスしてくれれば、私は美しいお姫様になります.それから、私はあなたの妻になりたいです.」男はまたカエルを出して、それに向かってかすかに笑って、ポケットに戻しました.「キスしてくれれば、私は美しいお姫様になります.それから、私はあなたの妻になりたいです.そして、あなたは私に何でもすることができます.」もう一度、男はカエルを出して、それに向かってかすかに笑って、ポケットに戻しました.最后に、カエルは力がなくて闻きます:“私はこんなに良い条件を出して、どうしてあなたはまだ私にキスしませんか?”男の人は言います:“私はプログラマーで、私はどんな王女とごろつきをする时間がありません.しかし、1つの话すことができるカエルを持って、とてもクールです.”
--------------------------------------オリジナル記事By列挙とステータス-------------------------------
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列挙とステータス-------------------------------