[C++知识库]四大湖比大小

这题目我就想练练用二进制做。
大体思路是 用四个1111: 1111 1111 1111 1111代表四个湖泊的所有可能性 比如说 鄱阳湖的可能性为1111（15）这个二进制标记意味着它可能是第一名 可能是第二名 可能是第三名 可能是第四名。
从左边数第一位代表是否有可能是第一名 右边第一位表示是否可能是最后一名
再从每个人说的话中排除可能性
比如说 洞庭湖最初是1111 假设A第一句是对的 其他两句是错的 那么洞庭湖的1111就会变成1000（按位取与）
那他说的洪泽湖最小就是错的 也就是说洪泽湖不可能最小 直接用最小0001取反1110 再与最初的洪泽湖1111取与 就变成1110
利用深度优先搜索把每句话叠合在一起。

#include <stdio.h>
#include <stdbool.h>
#define N1 8
#define N2 4
#define N3 2
#define N4 1
char ans[4][15]={"洞庭湖","洪泽湖","鄱阳湖","太湖"};
bool e0(int p[]){	//数组中是否存在0
	if(p[0]&&p[1]&&p[2]&&p[3])return false;return true;}
bool finish(int p[]){ //判断是否找到了：一个1000 一个0100 一个0010 一个0001
	if((p[0]+p[1]+p[2]+p[3]==15)&&(p[0]|p[1]|p[2]|p[3]==15)&&!(p[0]&p[1]&p[2]&p[3])){
		int k=16;
    	while(k>>=1)for(int i=0;i<4;i++)if(p[i]==k)printf("%s\n",ans[i]);
    	return true;
  	}return false;
}
void judge(int p []){  //判断当前数组是否能化为解 存在0时或无法继续化时放弃
	if(e0(p)||finish(p))return;
	int i;
	for(i=0;i<4;i++)
	if(p[i]==N1||p[i]==N2||p[i]==N3||p[i]==N4)break;
  	if(i==4)return;
  	for(int j=0;j<4;j++)
    	if(j!=i&&p[j]==(p[j]|p[i]))p[j]=p[j]^p[i];
 	judge(p);
} 
//对guess深度优先搜索 index记为层数 p记可能性
void DFS(int guess[][4],int index,int p[]){ 
	if(e0(p))return;
  	if(index==4){judge(p);return;}  
  	for(int i=0;i<4;i++){
    int q[4];
	for(int j=0;j<4;j++)
    	if(i!=j)q[j]=p[j]&(15-guess[index][j]);
      	else q[j]=p[j]&guess[index][j];
    DFS(guess,index+1,q);
  }
}
int main(){//guess存四人的话。顺序：洞 洪 鄱 太.例如第一个人觉得洞1洪4鄱3 就存入N1 N4 N3 不说太湖补0
	int guess[4][4]={{N1,N4,N3},{N4,N1,N2,N3},{N3,N4},{N3,N2,N1,N4}};
  	int p[4]={15,15,15,15}; //p记可能性 看二进制 (12)1100意思是可能是第一或第二
  	DFS(guess,0,p);
  	return 0;
}