学步园

这道题有两个重要的地方，一个是对题目的理解，合法的操作只有一种，那就是对相邻的两个状态不同的灯泡进行交换状态的操作，也就是说，相邻的灯泡如果都是亮着的或者暗着的，那么不能对这条边进行操作。

第二点，那就是由于所有的状态的目标状态都是一样的，那么我们就可以从目标状态进行BFS，计算出其他状态到目标状态要多少步，注意当BFS的步数大于3的时候，就不要将其子状态放入队列中，为了方便，之前将全部的状态的需要步数设置为5，这样即使没有访问的状态，步数也是大于3的，这个算法的时间复杂度是O(32^3)，完全可以接受，之后就是O(1)的查询。

为了方便BFS，优化空间，运用位压缩，将16个灯泡的状态用一个int来存放，高位存放低编号的灯泡，装换的时候就用异或运算即可。

数组x和y用来对应32对相邻的灯泡

我的代码：

#include <iostream><br /> #include <cstdio><br /> #include <cstring><br /> #include <cstdlib><br /> #include <queue></p> <p>using namespace std;</p> <p>const int MAX=1<<17;<br /> const int x[32]={0,1,3,11,10,8,10,2,8,9,9,0,0,1,3,11,10,8,9,2,12,13,13,4,14,6,12,4,5,7,15,14};<br /> const int y[32]={1,3,11,10,8,0,2,3,9,1,11,2,4,5,7,15,14,12,13,6,13,5,15,6,6,7,4,5,7,15,14,12};<br /> const int aim=((1<<8)-1);<br /> int dist[MAX];</p> <p>struct Node<br /> {<br /> int st;<br /> int depth;<br /> };</p> <p>int hash(const int& st,const int& op)<br /> {<br /> return st^((1<<(15-x[op]))|(1<<(15-y[op])));<br /> }</p> <p>void bfs()<br /> {<br /> Node node,next;<br /> queue<Node> q;</p> <p> node.st=aim;<br /> node.depth=0;<br /> dist[aim]=0;<br /> q.push(node);<br /> while(!q.empty())<br /> {<br /> node=q.front();<br /> q.pop();<br /> if(node.depth>3)<br /> break;<br /> next.depth=node.depth+1;<br /> for(int i=0;i<32;i++)<br /> {<br /> if((node.st&(1<<(15-x[i])))!=(node.st&(1<<(15-y[i]))))<br /> {<br /> next.st=hash(node.st,i);<br /> if(dist[next.st]==1000)<br /> {<br /> dist[next.st]=next.depth;<br /> q.push(next);<br /> }<br /> }<br /> }<br /> }<br /> }</p> <p>int main()<br /> {<br /> int t,cnt=0;<br /> int a;<br /> int st;</p> <p> for(int i=0;i<MAX;i++)<br /> {<br /> dist[i]=1000;<br /> }<br /> bfs();</p> <p> scanf("%d",&t);<br /> while(t--)<br /> {<br /> cnt++;<br /> st=0;<br /> for(int i=0;i<16;i++)<br /> {<br /> scanf("%d",&a);<br /> if(a==1)<br /> st|=(1<<(15-i));<br /> }</p> <p> a=dist[st];<br /> if(a>3)<br /> {<br /> printf("Case #%d: more/n",cnt);<br /> }<br /> else<br /> {<br /> printf("Case #%d: %d/n",cnt,a);<br /> }<br /> }</p> <p> return 0;<br /> }<br />

总结：在搜索的时候，我们经常要想到是否有可以优化的方法，位压缩是一个很好的节约空间的方式，另外，这题不可能对每个状态正向BFS，那样在多case的情况下肯定是TLE的，另外就是要仔细看题，理解题目的意思，对题目的理解如果错误，将会导致思路的定式，觉得自己肯定是对的，这样，在比赛的时候就会心慌，严重影响比赛的状态。