Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:BFS+二进制

Posted by Xian_ll at 2023-04-20 20:55:22 on Problem 1753
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator