Java(javac 1.8) 解法, 执行用时: 67ms, 内存消耗: 13196K, 提交时间: 2020-02-21 23:59:20

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static public void main(String[] args) {
		
		Scanner scan=new Scanner(System.in);
		n=scan.nextInt();
		scan.nextLine();
		String str=scan.nextLine();
		int result=0;
		for(int i=0;i<n;i++) {
			result|=1<<i;
			int f=(str.charAt(i)=='Y')?1:0;
			nowA|=f<<(i);
			nowB|=f<<(i);
		}
		trust=new int[n];
		for(int i=0;i<n;i++) {
			str=scan.nextLine();
			for(int j=0;j<n;j++) {
				int f=(str.charAt(j)=='Y')?1:0;
				trust[i]|=f<<(j);
			}
		}
        scan.close();
		int days=0;
		array=new ArrayList<Integer>();
		array.add(nowA);
		array.add(nowB);
		while(true) {
			ArrayList<Integer> copy=array;
			array=new ArrayList<Integer>();
			for(int i=0;i<copy.size();i+=2) {
				nowA=copy.get(i);
				nowB=copy.get(i+1);
				if(nowA!=0&&nowB!=0) {
					dfs(0,nowA,nowB);
					if(nowA==result&&nowB==result) {
						System.out.println(days);
						return;
					}
				}
			}
			days++;
			if(array.isEmpty()) {
				System.out.println("-1");
				break;
			}
		}
		
	}
	static int n;
	static int nowA=0;
	static int nowB=0;
	static int[] trust;
	static ArrayList<Integer> array;
	static void dfs(int oier,int A,int B) {
		if(oier>=n) {
			if((nowA^A)!=0||(nowB^B)!=0) {
				boolean flag=true;
				for(int i=0;i<array.size();i+=2) {
					if((A&(~array.get(i)))!=0||(B&(~array.get(i+1)))!=0) {
					}
					else {flag=false;break;}
				}
				if(flag) {
					for(int i=0;i<array.size();i+=2) {
						if((array.get(i)&(~A))==0&&(array.get(i+1)&(~B))==0) {
							array.set(i, 0);
							array.set(i+1, 0);
						}
					}
					array.add(A);
					array.add(B);
				}
			}
			return;
		}
		boolean flag=true;
		if((nowA&(1<<oier))!=0&&A!=(A|trust[oier])) {
			flag=false;
			dfs(oier+1,A|trust[oier],B);
		}
		if((nowB&(1<<oier))!=0&&B!=(B|trust[oier])) {
			flag=false;
			dfs(oier+1,A,B|trust[oier]);
		}
		if(flag) {
			dfs(oier+1,A,B);
		}
	}
}

C++ 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2022-05-12 21:25:49

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
map<pair<int,int>,int> d,vis;
queue<pair<int,int> > c;     
 int n;
 int a[30][30];
 void dfs(int all,pair<int,int> x1,pair<int,int> x2){//二进制存储状态
 	if(all==n+1){
 		if(!d.count(x2)){//核心函数count
 		d[x2]=d[x1]+1;//x2为后一天状态
 		c.push(x2);
		 }
		 return ;
	 }
	 int p1=(x1.first>>all)&1;
	 int p2=(x1.second>>all)&1;//这里应该是x1，x1为前一天状态，all指枚举到的位数
	 int u=x2.first;//a谎言的传播状态
	 int b=x2.second;	//b谎言的传播状态
	 for(int i=1;i<=n;i++){
	 	if(a[all][i]){
	 		if(p1) u=u|(1<<i);//最难的地方 |或操作使得二进制i位置有1不变，没1加1，其他位置不变
	 		if(p2) b=b|(1<<i);
		 }
	 }
	 if(u==x2.first&&b==x2.second) dfs(all+1,x1,x2);
	 if(u!=x2.first) dfs(all+1,x1,make_pair(u,x2.second));//一次只能传播a或b谎言
	 if(b!=x2.second) dfs(all+1,x1,make_pair(x2.first,b));
 }
 int ans=0;
 int bfs(){
 	while(!c.empty()){
 		pair<int,int> l=c.front();	
		 //cout<<l.first<<" "<<l.second<<endl;
 		c.pop();
 		
 		vis[l]=1;
 		dfs(1,l,l);
	 }
	 for(int i=1;i<=n;i++){
	 	ans+=(1<<i);
	 }
	 if(vis[make_pair(ans,ans)]==0) return 0;
	 else return 1;
 }
int main() {
	cin>>n;
	string s;
	cin>>s;
	int w=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='Y')
		w+=(1<<(i+1));
	}
	d[{w,w}]=0;
	c.push({w,w});
	char o;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++){
		cin>>o;
		if(o=='Y')
	a[i][j]=1;
	}

	if(bfs()) cout<<d[{ans,ans}]<<endl;
	else cout<<"-1"<<endl;

    return 0;
}