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:Xian_ll at 2023-04-20 20:54:45 > #include<iostream> > #include<string> > > using namespace std; > > // 16个棋子翻棋,使他全白或全黑,翻一个则上下左右全翻 > > const int mx = 1<<16; > int f[mx] = {0}; > int pre[mx] = {0}; > int qu[mx],e = -1,s = 0; > string str[5]; > int b[5] = {0,1,-1,4,-4}; > > void pri(int t){ > int ff = 15; > for(int i = 1;i<=4;++i){ > for(int j = 1;j<=4;++j){ > cout << ((t&1<<ff)?1:0) << " "; > --ff; > } > cout <<endl; > } > cout <<endl; > } > > int main(){ > for(int i = 1;i<=4;++i){ > cin >> str[i]; > } > int st = 0; > for(int i = 1;i<=4;++i){ > for(int j = 0;j<4;++j){ > st<<=1; > if(str[i][j]=='b')++st; > } > } > qu[++e] = st; > f[st] = 1; > int cur,nx,np; > while(s<=e){ > if(f[0]) break; > cur = qu[s++]; > for(int i = 15;i>=0;--i){ > nx = cur; > for(int j = 0;j<5;++j){ > if(i%4==3 &&j==1) continue; > if(i%4==0 && j==2) continue; > np = i+b[j]; > if(np<0 || np>15) continue; > nx^=(1<<np); > } > if(!f[nx]){ > f[nx] = f[cur]+1; > pre[nx] = cur; > qu[++e] = nx; > if(nx==0) break; > } > } > } > if(f[0] || f[(1<<16)-1]){ > cout << min(f[0],(f[(1<<16)-1]>0?f[(1<<16)-1]:0x3f3f3f3f))-1; > }else > cout << "Impossible"; > > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator