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 |
麻烦哪位大牛也好 小牛也好 帮忙看一下我的BFS+位运算为什么超时 谢谢#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int N=70000; int a[6][6]={0}; int change[5][5]={{0},{0,0xf888,0xf444,0xf222,0xf111},{0,0x8f88,0x4f44,0x2f22,0x1f11},{0,0x88f8,0x44f4,0x22f2,0x11f1},{0,0x888f,0x444f,0x222f,0x111f}}; int que[700000]; int pre[N]={0},c[N],r[N],step[N]; int flag[N]={0}; int ans1[N],ans2[N]; int main() { //freopen("data.in.txt","r",stdin); int i,j; int k=0; char d; for(i=1;i<=4;i++) { for(j=1;j<=4;j++) { scanf("%c",&d); if(d=='+') k+=1<<(16-(i-1)*4-j); } getchar(); } int p=0,q=0,t,state; que[p++]=k; pre[k]=-1; while(q<=p) { t=que[q]; if(t==0) break; if(flag[t]==0) { flag[t]=1; for(i=1;i<=4;i++){ for(j=1;j<=4;j++) { state=t^change[i][j]; if(!flag[state]) { que[p++]=state; pre[state]=t; r[state]=i; c[state]=j; step[state]=step[t]+1; if(state==0) break; } } if(state==0) break; } if(state==0) break; } q++; } cout<<step[0]<<endl; t=0; for(i=1;i<=step[0];i++) { ans1[i]=r[t]; ans2[i]=c[t]; t=pre[t]; } for(i=1;i<=step[0];i++) cout<<ans1[i]<<" "<<ans2[i]<<endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator