poj 1753 Flip Game & poj2965 - c++编程基础

用位操作+BFS+枚举解决.基本思想如下:

给棋盘每一个状态赋予一个状态id,id计算方法是将棋盘与数的二进制表示联系起来,如题所给的数据:

bwwb

bbwb

bwwb

bwww

状态id为6585,计算方法为1*2^0+0*2^1+0*2^2..1*2^12+0*2^13..=6585(其中b代表1,w代表0)

在此基础上进行BFS搜索,

1）总的状态数是一定的，共0~~65535=65536种状态；

2）首先理解一点,先点(0,0)再点(0,1)与先点(0,1)再点(0,0)对结果不造成任何影响.因此遍历棋盘的16个位置,将每次点击后的状态id利用树状结构保存.如:

6585

/ | \ ...

(0,0) (0,1) (0,2)

/ | \ ...

6568 6553 6646

...............................

对此树进行BFS搜索,将id为0(全白)或65535(全黑)的时候则搜索成功,输出树的高度；当队列为空，仍当未搜索成功时，则输出"Impossible".

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 1000000
using namespace std;
//BFS+枚举有限的状态数:2^16=65536种
int que[N];
int flag[65536];
int step[65536];
int front=0,rear=0;
//翻转某位，只需将该位与1抑或 
int flip(int state,int pos)  //翻转pos及其周围位置
{
   state^=(1<=0)   state^=(1<<(pos-4));   //翻转上方 
   if((pos+4)<=15)  state^=(1<<(pos+4));   //翻转下方 
   if(pos%4!=0)     state^=(1<<(pos-1));   //翻转左方 
   if(pos%4!=3)     state^=(1<<(pos+1));   //翻转右方 
   return state;
}
//广搜
int bfs()
{
   int tag=0,state,temp; 
   while(front

这道题是搜了题解之后才写出来的，刚开始总是不知道该如何枚举，忽略了状态数是有限的这一条件。

做完这道，再去做poj2965 http://poj.org/problem id=2965 ，就简单多了。唯一不同的就是多了保存搜索路径；我能想到的就是保存当前状态的前一个状态，以及前一个状态到达当前状态的路径值；总体感觉空间效率有点儿低。。。附上代码:

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define N 1000000  
using namespace std;  
char s[5];  
int que[N];  
int flag[65536];  
int step[65536];  
struct stpath{  
  int prest;  
  int ps;         
}pp[65536];   //保存路径  
struct path{  
  int x;  
  int y;         
}r[65536];  
int initial()    //初始化   
{  
  int state=0;  
  for(int i=0;i<4;i++){  
    scanf("%s",s);  
    for(int j=0;j<4;j++){  
      if(s[j]=='+')  
        state|=1<<(i*4+j);     //求初始状态                          
    }          
  }   
  return state;        
}  
int switching(int temp,int pos)   //状态翻转   
{  
     temp^=(1<=0;i--){  
    printf("%d %d\n",r[i].x,r[i].y);         
  }  
  //system("pause");  
  return 0;  
}