Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
唉,为什么我的怎么慢啊:(#include<iostream> #include<algorithm> using namespace std; #define max 65536 struct node { bool map[4][4]; int step; }q[max*2]; int visit[max],tar1=0,tar2=max-1; int pow2[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768}; /*void init() { int m=1; for(int i=0;i<16;i++) { pow2[i]=m; m*=2; } }*/ int trans(bool a[4][4]) { int m=0; for(int i=0;i<16;i++) { m=m+a[i/4][i%4]*pow2[i]; } return m; } int bfs(node s) { int h=0,t=1; q[h]=s; q[h].step=0; visit[trans(s.map)]=1; node cur,next; while(h<t) { cur=q[h]; if(trans(cur.map)==tar1||trans(cur.map)==tar2) { return cur.step; } for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { next=cur; if(i>0) { next.map[i-1][j]=!cur.map[i-1][j]; } if(i<3) { next.map[i+1][j]=!cur.map[i+1][j]; } if(j>0) { next.map[i][j-1]=!cur.map[i][j-1]; } if(j<3) { next.map[i][j+1]=!cur.map[i][j+1]; } next.map[i][j]=!cur.map[i][j]; if(!visit[trans(next.map)]) { next.step=cur.step+1; q[t++]=next; visit[trans(next.map)]=1; } } } h++; } return -1; } int main() { // init(); node cur; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { char c; cin>>c; c=='w'?cur.map[i][j]=1:cur.map[i][j]=0; } } memset(visit,0,sizeof(visit)); int k; k=bfs(cur); if(k==-1) { cout<<"Impossible"<<endl; } else { cout<<k<<endl; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator