首页 > 代码库 > 【POJ1753】Flip Game

【POJ1753】Flip Game

2024-07-06 01:24:04   230人阅读

【题目大意】

有一个4x4规格的一个棋盘，现在有16个一面黑一面白的棋子分布在这个棋盘上。

翻转一个棋子能够使它以及它上下左右的四个棋子从黑变白，从白变黑。

现在问你至少要经过多少次操作才能够使得整个棋盘的颜色相同。

【分析】

考虑到是4x4的规模，想到用BFS枚举+判重。

注意题目的内存限制是64MB，如果普通的用一个二维数组记录状态可能会超过内存限制。

考虑位运算，下面给出AC代码。

 

 1 #include <iostream>
 2 #include <fstream>
 3 #include <string>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <queue>
 7 const int INF=0x7fffffff;
 8 using namespace std;
 9 struct map
10 {
11      int shu[6];//位运算按行存储 
12      int times;//翻转次数 
13      map(){memset(shu,0,sizeof(shu));}
14 }data;
15 bool hash[(1<<16)+10];//哈希表 
16 
17 bool test(map t);//检测 
18 map change(map t,int x,int y);
19 void print();//检测函数 
20 int bfs();//广搜
21 int h(map t);//哈希函数 
22 
23 int main()
24 {
25     int i,j; 
26     //文件操作
27     //freopen("data.txt","r",stdin);
28     //freopen("out.txt","w",stdout);
29     memset(data.shu,0,sizeof(data.shu));
30     
31     //读入数据 
32     for (i=1;i<=4;i++)
33     { 
34         if (i!=1) getchar(); //读取换行符 
35         for (j=1;j<=4;j++)
36         {
37             char temp;
38             scanf("%c",&temp);
39             //注意这里存储是从左向右存储 
40             if (temp==‘w‘) data.shu[i]=(data.shu[i]<<1)+1;
41             else data.shu[i]=(data.shu[i]<<1)+0;
42         } 
43     } 
44     int ans=bfs();
45     if (ans==INF) printf("Impossible\n");
46     else printf("%d",ans);
47     return 0;
48 }
49 bool test(map t)//检测函数 
50 {
51      int cnt=0,i,j;
52      for (i=1;i<=4;i++) cnt+=t.shu[i];
53      if (cnt==0 || cnt==(15*4)) return 1;
54      return 0;
55 }
56 int bfs()
57 {
58     queue<map>Q;
59     memset(hash,0,sizeof(hash));
60     int i,j;
61     data.times=0;
62     hash[h(data)]=1;
63     Q.push(data);//加入队列 
64     while (!Q.empty())
65     {
66           map u=Q.front();Q.pop();
67           if (test(u)) return u.times;
68           for (i=1;i<=4;i++)
69           for (j=1;j<=4;j++)
70           {
71               map v=u;
72               v=change(v,i,j);
73               v.times=u.times+1;
74               if (test(v)) return v.times;
75               if (hash[h(v)]==1) continue;//哈希判重
76               Q.push(v);
77               hash[h(v)]=1;
78           }
79     }
80     return INF;
81 }
82 int h(map t)//哈希函数 
83 {
84     int temp=0,i,j;
85     for (i=1;i<=4;i++) temp=(temp<<4)+t.shu[i];
86     return temp;
87 }
88 //第x行，第y个 
89 map change(map t,int x,int y)
90 {
91     t.shu[x]=((t.shu[x])^(1<<(4-y)));//本身
92     t.shu[x+1]=((t.shu[x+1])^(1<<(4-y)));//上面 
93     t.shu[x-1]=((t.shu[x-1])^(1<<(4-y)));//下面 
94     if (y!=1) t.shu[x]=((t.shu[x])^(1<<((4-y)+1)));//左边 
95     if (y!=4) t.shu[x]=((t.shu[x])^(1<<((4-y)-1)));//右边 
96     return t;
97 }
View Code

 


联系
我们