ALGO-114 黑白无常

Love The Way You Lie 2022-03-16 12:16 150阅读 0赞

问题描述  
　　某寝室的同学们在学术完之后准备玩一个游戏：游戏是这样的，每个人头上都被贴了一张白色或者黑色的纸，现在每个人都会说一句话“我看到x张白色纸条和y张黑色的纸条”，又已知每个头上贴着白色纸的人说的是真话、每个头上贴着黑色纸的人说的是谎话，现在要求你判断哪些人头上贴着的是白色的纸条，如果无解输出“NoSolution.”；如果有多组解，则把每个答案中贴白条的人的编号按照大小排列后组成一个数（比如第一个人和第三个人头上贴着的是白纸条，那么这个数就是13；如果第6、7、8个人都贴的是白纸条，那么这个数就是678）输出最小的那个数（如果全部都是黑纸条也满足情况的话，那么输出0）  
输入格式  
　　第一行为一个整数n，接下来n行中的第i行有两个整数x和y，分别表示第i个人说“我看到x张白色纸条和y张黑色的纸条”。  
输出格式  
　　一行。如果无解输出“NoSolution.”。否则输出答案中数值（具体见问题描述）最小的那个，如果全部都是黑纸条也满足情况的话，那么输出0  
样例输入  
2  
1 0  
1 0  
样例输出  
0  
样例输入  
5  
3 1  
0 4  
1 3  
4 0  
1 3  
样例输出  
35  
数据规模和约定  
　　n<=8

每个人只有两种可能  真或假

所以一共暴力出所有    2的n次方    种方案数

/*
    解题思路：
    dfs枚举2^n个可能，代表1-n个人的说法，用判断函数判断，若都没有，则无解 
    */
    #include <iostream>
    using namespace std;
    struct person{
    	int x,y;
    }a[15];
    int n;
    int mark[10]; //标记  0白纸 1黑纸 
    
    int minn=999999;//输出结果 
     
    int white(int x){   //检查除自己外有多少白色 
    	int j,sum=0;
    	for(j=1;j<=n;j++){
    		if(j==x)
    		continue;
    		if(mark[j]==0)
    		   sum++;
    	}
    	return sum;
    }
    int black(int y){     //检查除自己外有多少黑色 
    	int j,sum=0;
    	for(j=1;j<=n;j++){
    		if(j==y)
    		continue;
    		if(mark[j]==1)
    		   sum++;
    	}
    	return sum;
    } 
     
    bool check(){
    	int i;
    	for(i=1;i<=n;i++){
    		if(mark[i]==0){    //白纸就得说真话 
    			if(white(i)!=a[i].x||black(i)!=a[i].y)
    			   return false;
    		}
    		else{      //黑纸就得说假话 
    			if(white(i)==a[i].x&&black(i)==a[i].y)
    			   return false;
    		}
    	}
    	return true;
    }
    //  0白纸 
    void dfs(int now){
    	if(now==n){
    		if(check())   //如果符合存进去 
    		{
    		   int tmp=0,i;
    		   for(i=1;i<=n;i++){
    		   	  if(mark[i]==0)      //计算白纸条合成数字 因为可能存在多种方案所以不能直接输出编号 
    		   	  tmp=tmp*10+i;		 
    		   }
    		   minn=min(minn,tmp);		        
    		}	
    		return ;
    	}
    	mark[now]=0;     //白色 
    	dfs(now+1);
    	mark[now]=1;        //黑色 
    	dfs(now+1);
    }
    int main(){
    	int i;
        cin>>n; 
       	   for(i=1;i<=n;i++)
       	     cin>>a[i].x>>a[i].y;
    	    dfs(0);
    		 if(minn==999999)
    		   cout<<"NoSolution."<<endl;
    		   else{
                  cout<<minn<<endl;
    		   }
    	return 0;
    }