ZOJ 3814 Sawtooth Puzzle 状态压缩搜索 - c++编程基础

TOP

ZOJ 3814 Sawtooth Puzzle 状态压缩搜索

2015-07-20 17:44:19 来源: 作者: 【大中小】浏览:2次

Tags：ZOJ 3814 Sawtooth Puzzle 状态压缩搜索

由于一个框框只有4种状态，总状态数只有4^9，bfs可解。

麻烦的地方就在于模拟。

我的状态的存法是，将初始状态看做000000000，若顺时针旋转一次就+1， 3+1=0。

bfs的过程中，需要套一个dfs计算旋转当前框框会影响到哪些框。

有个地方要注意，就是目标状态其实不止一种，因为有些框框旋转之后不变，我们必须把所有可能的目标状态都计算出来，样例的中间那个框框就是这种情况。

#include 
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           using namespace std; #define maxn 100005 int h[15]; struct node { int x,dis; }t,f; char st[10][10][10]; char ed[10][10][10]; char tst[10][10]; char tzf[10][10]; vector
          
            fin[15]; int edge[10][4]; struct fuck { int to,turn; fuck(int a,int b){to=a;turn=b;} fuck(){} }v[20]; int top; bool use[15]; bool FINAL[1111111]; void cal(int now) { memcpy(tst,st[now],sizeof(st[now])); for(int d=0;d<4;d++) { if(memcmp(tst,ed[now],sizeof(tst))==0) {fin[now].push_back(d);} for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { tzf[j][8-i-1]=tst[i][j]; } } memcpy(tst,tzf,sizeof(tzf)); } } bool vis[1111111]; int Turn[9]; bool isok(int x,int y) { return x>=0&&x<3&&y>=0&&y<3; } int dx[]={0,-1,0,1}; int dy[]={-1,0,1,0}; int op(int a,int b) { if(a-b>=0) return a-b; return 3-(b-a-1); } bool can(int a,int b,int d) { if(d==0&&edge[a][op(0,Turn[a])]&&edge[b][op(2,Turn[b])]) return true; if(d==1&&edge[a][op(1,Turn[a])]&&edge[b][op(3,Turn[b])]) return true; if(d==2&&edge[a][op(2,Turn[a])]&&edge[b][op(0,Turn[b])]) return true; if(d==3&&edge[a][op(3,Turn[a])]&&edge[b][op(1,Turn[b])]) return true; return false; } void dfs(int x,int y,int flag) { v[top++]=fuck(x*3+y,flag); for(int d=0;d<4;d++) { int nx=x+dx[d]; int ny=y+dy[d]; if(isok(nx,ny)&&use[nx*3+ny]==0&&can(x*3+y,nx*3+ny,d)) { use[nx*3+ny]=true; dfs(nx,ny,-flag); } } } void bfs() { memset(Turn,0,sizeof(Turn)); memset(vis,0,sizeof(vis)); vis[0]=true; queue
           
             q; f.dis=0;f.x=0; q.push(f); while(!q.empty()) { f=q.front();q.pop(); for(int i=0;i<9;i++) Turn[i]=(f.x/h[9-i-1])%4; for(int d=0;d<9;d++) { t=f; t.dis++; top=0; memset(use,0,sizeof(use)); use[d]=1; dfs(d/3,d%3,1); int tmp=t.x; for(int i=0;i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：ZOJ 3811 Untrusted Patrol 并查集	下一篇：Chrome插件开发小插件-acfun看图..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: