infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
用16个为存储棋盘的状态,BFS时,每次枚举所有可能的变换。




Source Code

Problem: 1753
User: lovecanon
Memory: 732K
Time: 32MS
Language: C
Result: Accept
  • Source Code

  • #include<stdio.h>
    #include
    <string.h>
    unsigned 
    int queue[65536],vis[65536],step[65536];
    int main()
    {
        unsigned 
    int i,j,k=1<<15,front=0,rear=0,cnt,tmp;
        queue[
    ++rear]=0;
        
    for(i=0;i<4;i++)
        {
            
    for(j=0;j<4;j++)
            {    
                queue[rear]
    +=(getchar()=='b')*k;
                k
    >>=1;
            }
            getchar();
        }
        
    if(queue[rear]==0||queue[rear]==65535) {printf("0\n");return 0;}
        step[queue[rear]]
    =0;
        memset(vis,
    0,sizeof(vis[0]));
        vis[queue[rear]]
    =1;
        
    while(front<rear)
        {
            cnt
    =queue[++front];
            
    for(i=0;i<4;i++)
                
    for(j=0;j<4;j++)
                {   
                    tmp
    =cnt;
                    
    if(i==0)  tmp^=0x1<<(11-4*i-j);
                    
    else if(i==3)  tmp^=0x1<<(19-4*i-j);
                    
    else {tmp^=0x1<<(19-4*i-j);tmp^=0x1<<(11-4*i-j);}
                    
    if(j==0)  tmp^=0x3<<(14-4*i);   
                    
    else if(j==3)  tmp^=0x3<<(12-4*i);
                    
    else tmp^=0x7<<(14-4*i-j);    
                    
    if(tmp==0||tmp==65535) {printf("%d\n",step[cnt]+1); return 0;}
                    
    else if(!vis[tmp])
                    {queue[
    ++rear]=tmp; step[tmp]=step[cnt]+1;vis[tmp]=1;}
                }
        }   
        printf(
    "Impossible\n");
        
    return 0;
    }

posted on 2008-09-20 04:29 infinity 阅读(1005) 评论(2)  编辑 收藏 引用 所属分类: acm

评论

# re: poj 1753 Flip Game 2009-08-07 13:22 longniu
妙!   回复  更多评论
  

# re: poj 1753 Flip Game 2010-04-14 15:08 祝你好运
写的确实是不错!如果能加上注释就更好了!  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理