POJ 1753

Posted on | In , | Visitors:

This is my blog.
poj.1753

题目：Flip Game

题意：有十六个棋子，初始状态给你，让你翻棋子，使之全黑或全白。翻棋子的规则为，其上下左右和自己都会翻一翻。

idea：

1.BFS法：十六个棋子，两种状态，就可以用0 1 表示状态，用二进制来表示，那么2^15约为32768，可以用int来表示,每一个数字表示一种情况。

2.枚举法：可以对第一行进行枚举，则有2^4种可能性，然后下面一行来配合第一行，一个一个修改，看是否最后能够成功。

AC代码：

1.BFS法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
queue<int>q;
const int maxn=65535;
int a=0,flag=0;
<!--bool visited[maxn+10]={0};  //标记此种状态是否达到过
int cnt[maxn+10]={0};   //cnt记录达到此种状态的最小步数
int BFS(){
if(a==0||a==maxn){
flag=1;
return 0;
}
visited[a]=1;
cnt[a]=0;
q.push(a);
while(!q.empty()){
a=q.front();
q.pop();
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
int x;
x=a;    
if(i==0)//change (1,j)
x^=1<<(15-4*(i+1)-j);
else if(i==3)//change (2,j)
x^=1<<(15-4*(i-1)-j);
else{
x^=1<<(15-4*(i+1)-j);
x^=1<<(15-4*(i-1)-j);
}
if(j==0)//change (i,1)
x^=3<<(15-4*i-(j+1));
else if(j==3)//change (i,2)
x^=3<<(15-4*i-j);
else{
x^=3<<(15-4*i-(j+1));
x^=3<<(15-4*i-j);
x^=1<<(15-4*i-j);
}//change (i,j-1) and (i,j+1)
if(x==0||x==maxn){
flag=1;return cnt[a]+1;
}
if(!visited[x]){
cnt[x]=cnt[a]+1;
visited[x]=1;
q.push(x);
}
}
}
}
}
int main(){
char b[8];
for(int i=0;i<4;i++){
scanf("%s",b);
for(int j=0;j<4;j++){
a<<=1;
if(b[j]=='b') a+=1;//black用1表示
}
}
int ans=BFS();
if(!flag)
printf("Impossible\n");
else
printf("%d\n",ans);
}
/*测试数据
bwbb
wwwb
bwbb
bbbb
1011 0001 1011 1111 45503
0111 1001 1011 1111 31167
1101 0101 1011 1111 54719
*/

2.枚举法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[6][6];
int a[6];
int ans;
int kai[6], b[6];
int calc(){
int cnt = 0;
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
if ((kai[i] >> j) & 1)
cnt++;
}
}
return cnt;
}
void deal(){
int tmp = 0;
for (int i = 0; i < 16; i++){  //16种情况
kai[0] = i;
b[0] = a[0] ^ i ^ ((i <<1) & 15 ) ^ (i >> 1);   //翻第一行的棋子
b[1] = a[1] ^ i;  //翻了第一行后对第二行的影响
for (int j = 1; j <= 3; j++){  
kai[j] = b[j-1];  //根据前一行来翻棋子
b[j] = b[j] ^ kai[j] ^ ((kai[j]<<1)&15) ^ (kai[j]>>1);  //此行更改
b[j+1] = a[j+1] ^ kai[j];  //对下一行的影响
}
if (b[3] == 0){  //倒数第二行翻好后，最后一行应该为目标状态了
tmp = calc(); //计算步数
ans = min(ans, tmp);  //更新答案
}
}
}
int main(){
for (int i =0; i < 4; i++){
scanf(" %s", s[i]);
for (int j = 0; j < 4; j++){
if (s[i][j] == 'b'){
a[i] |= (1 << j); //a[i]初始均为0，每一行变为四位
}
}
}
ans = 0x7f; //给定一个max值
deal();
//换一种全黑的情况
for (int i = 0; i <= 4; i++){
a[i] = a[i] ^ 15;
}
deal();
if (ans  > 16)
printf("Impossible\n");
else printf("%d\n", ans);
return 0;
}

转载请注明出处，谢谢。

愿 我是你的小太阳



买糖果去喽