POJ 1166 The Clocks [BFS] [位运算]

1.题意：有一组3*3的只有时针的挂钟阵列，每个时钟只有0,3,6,9三种状态；对时针阵列有9种操作，每种操作只对特点的几个时钟拨一次针，即将时针顺时针波动90度，现在试求从初试状态到阵列全部指向0的状态所需要的最小操作数的操作方案；

2.输入输出：输入给出阵列初始状态，0,1,2,3分别表示0,3,6,9；要求输出最快方案的操作序列；

3.分析：IOI 1994的考题，BFS是比较容易想到的方法之一，关键是如何简洁的表示和改变BFS过程中的阵列状态；这里使用位运算的方法；具体如下：

首先一共9个时钟，每个时钟有0,1,2,3这4种状态，所以每个时钟可以由两位二进制数表示，则整个阵列就可以用18位二进制数表示，这里表示的问题就解决了；下一步就是如何表示"转动90度了",这里分三步，1）从状态中取出要调整的那个钟，2）对取出的sub部分进行模拟转动90度的操作，3）将处理完的sub放回原状态；经过这样的三个步骤之后，对一个钟的修改就完成了，针对每种操作，对这个操作内的每个时钟进行修改，就对当前状态完成了操作；

综上所述，这样的位运算方法使得表示更加简洁，计算的更快；具体代码如下：

 # include <cstdio>

 # include <iostream>

 # include <queue>

 # include <cstring>

 # include <stack>

 using namespace std;

 const int MAXN=<<;

 int clock[];

 int vis[MAXN];

 struct Node

 {

     int status,move,pre;

     Node (){}

     Node(int ss,int mm,int pp)

     {

         status=ss;

         move=mm;

         pre=pp;

     }

 }L[MAXN];

 int M[][]=

 {{,,,,-},{,,,-,-},{,,,,-},

  {,,,-,-},{,,,,},{,,,-,-},

  {,,,,-},{,,,-,-},{,,,,-}};

 void Init()

 {

     for(int i=;i<;i++)

         scanf("%d",&clock[i]);

     memset(vis,,sizeof(vis));

 }

 void Solve()

 {

     queue<Node> Q;

     int start=;

     int len=;

     for(int i=;i<;i++)

         start|=(clock[i]<<(i<<));

     Q.push(Node(start,-,-));

     vis[start]=;

     while(!Q.empty())

     {

         Node temp=Q.front();

         Q.pop();

         L[len++]=temp;

         if(temp.status==)

             break;

         //printf("%d\n",temp.move);

         for(int i=;i<;i++)

         {

             int nclock=;

             int nstatus=temp.status;

             for(int j=;j<;j++)

                 if(M[i][j]>=)

                 {

                     nstatus&= ((<<)-) ^ (<<(*(M[i][j])));

                     //"1111[目标位]1111",把待处理部分位的位置清零

                     nclock=(temp.status >> (*(M[i][j]))) & ;

                     //取出要处理的部分位

                     nstatus|=((nclock+) & ) << (*(M[i][j]));

                     //填入处理后的部分位

                 }

             if(!vis[nstatus])

             {

                 Q.push(Node(nstatus,i,len-));

                 vis[nstatus]=;

             }

         }

     }

     len--;

     stack<int> S;

     while()

     {

         S.push(L[len].move+);

         len=L[len].pre;

         if(L[len].pre<)

             break;

     }

     printf("%d",S.top());

     S.pop();

     while(!S.empty())

     {

         int t=S.top();

         S.pop();

         printf(" %d",t);

     }

     printf("\n");

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     Init();

     Solve();

     return ;

 }

eg.位运算举例

1.两位二进制数表示一个状态，4个一组，即8位二进制数表示一组状态

2.要实现的操作，对第i+1个状态进行加一操作

3.大体思路：1）待处理状态num做一个副本n； 2）num把要处理掉的那一位挖空；3）把待处理单位sub从n取出；

4）对sub操作；5）把sub塞回去

 void Init()

 {

     int num=;

     for(int i=;i<;i++)

         num|=(Num[i]<<(i*));

 }

 void Change(int i)

 {

     int n=num;

     num&=((<<)-)^(<<(i*));

     //把要处理的那一位挖空为什么是3呢，因为二进制"11"为3，正好把两个二进制位"挖空"

     int sub=(n>>(i*))&;//这样除了最低的两位其他的都会与0做&运算，都扑街了

     sub+=;

     num|=(sub<<(*i));

 }

巴特西

POJ 1166 The Clocks [BFS] [位运算]

最新文章

热门文章