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+位运算+回溯路径,G++500MSIn Reply To:BFS+位运算+回溯路径,G++500MS Posted by:sanyaocangku at 2012-08-26 13:34:32 > #include<iostream> > #include<cstdio> > #include<cstring> > #include<queue> > using namespace std; > #define N 5 > int sd,key=0; > int vis[1<<16]; > int dir[16] = {4383,8751,17487,34959,4593,8946,17652,35064,7953,12066, > 20292,36744,61713,61986,62532,63624}; > struct node > { > int sum,num,step; > }cur; > struct path > { > int x,pre; > }p[100001]; > void f(int index) > { > if(index) > { > f(p[index].pre); > printf("%d %d\n",p[index].x/4+1,p[index].x%4+1); > } > } > void bfs() > { > int i,j,k; > cur.sum=sd; > cur.num=0; > cur.step=0; > p[1].pre=0; > queue<node>q; > q.push(cur); > while(!q.empty()) > { > node b=q.front(); > q.pop(); > if(b.sum==0) > { > printf("%d\n",b.step); > f(b.num); > return; > } > for(i=0;i<16;i++) > { > node a=b; > a.sum^=dir[i]; > if(!vis[a.sum]) > { > a.num=++key; > a.step++; > p[key].pre=b.num; > p[key].x=i; > q.push(a); > vis[a.sum]=1; > } > } > } > } > int main() > { > int i,j; > char s[5]; > for(i=0;i<4;i++) > { > scanf("%s",s); > for(j=0;j<4;j++) > { > if(s[j]=='+') > { > sd+=(1<<i*4+j); > } > } > } > bfs(); > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator