学步园

经过去除code变量加上手写队列，把代码的时间优化了不少，但是看了一下status，感觉压力很大，一帮的0ms。。。。

code是没用的记录，可以删除，成型代码如下：

#include <iostream><br /> #include <cstring><br /> #include <cstdlib><br /> #include <cstdio></p> <p>using namespace std;</p> <p>const int MAX=500000;<br /> struct Node<br /> {<br /> int table;<br /> int depth;<br /> int last;<br /> }start,queue[MAX];</p> <p>int hash(int table,int op)<br /> {<br /> int st;</p> <p> st=(1<<op);<br /> if(op%4>0)<br /> st|=(1<<(op-1));<br /> if(op%4<3)<br /> st|=(1<<(op+1));<br /> if(op/4>0)<br /> st|=(1<<(op-4));<br /> if(op/4<3)<br /> st|=(1<<(op+4));</p> <p> return (table^st);<br /> }</p> <p>int bfs()<br /> {<br /> Node node,next;<br /> int tail=0,head=0;</p> <p> node.table=start.table;<br /> node.depth=0;<br /> node.last=-1;<br /> if(node.table==0||node.table==((1<<16)-1))<br /> return 0;</p> <p> queue[head++]=node;<br /> while(head!=tail)<br /> {<br /> node=queue[tail];<br /> tail=(tail+1)%MAX;<br /> for(int i=node.last+1;i<16;i++)<br /> {<br /> next.table=hash(node.table,i);<br /> next.depth=node.depth+1;<br /> next.last=i;<br /> if(next.table==0||next.table==((1<<16)-1))<br /> return next.depth;<br /> queue[head]=next;<br /> head=(head+1)%MAX;<br /> }<br /> }</p> <p> return -1;<br /> }</p> <p>int main()<br /> {<br /> char str[10];</p> <p> start.table=0;<br /> for(int i=0;i<4;i++)<br /> {<br /> gets(str);<br /> for(int j=0;j<4;j++)<br /> {<br /> if(str[j]=='b')<br /> {<br /> start.table|=(1<<(i*4+j));<br /> }<br /> }<br /> }</p> <p> int ret=bfs();<br /> if(ret==-1)<br /> printf("Impossible/n");<br /> else<br /> printf("%d/n",ret);</p> <p> return 0;<br /> }<br />