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 |
Re:bfs~~用位运算压缩,附代码In Reply To:bfs~~用位运算压缩,附代码 Posted by:lzxzy at 2018-10-06 16:44:01 #include<cstdio> #include<cstdlib> #include<string.h> #include<math.h> #define X 0x7fffffff #define min(x,y) (x<y?x:y) char in[7]; bool check[100000]; int d[20]={0,0xc800,0xe400,0x7200,0x3100,0x8c00,0x4e00,0x2700,0x1300,0x08c8,0x04e4,0x0272,0x0131,0x008c,0x004e,0x0027,0x0013}; struct node{ int that; int ans; }qu[10000010]; void bfs(int s) { int minn=X; int head=1,tail=1; check[s]=1; qu[head].that=s; qu[head].ans=0; while(head<=tail) { for(int i=1;i<=16;i++) { int t=qu[head].that; int u=t^d[i]; if (check[u]!=1){ ++tail; check[u]=1; qu[tail].that=u; qu[tail].ans=qu[head].ans+1; if (u==65535||u==0) minn=min(minn,qu[tail].ans); } } head++; } if (minn!=X) printf("%d\n",minn); else printf("Impossible\n"); } int main() { int s=0; for(int i=1;i<=4;i++) { scanf("%s",in+1); for(int j=1;j<=4;j++) if (in[j]=='b') s=s*2+1; else s*=2; } bfs(s); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator