| ||||||||||
| 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