C++趣味算法之侦探推理

 
#include <bits/stdc++.h>
using namespace std;
 
//m：总人数  n：始终说谎人数  p：说话的总数
int m, n,  p;
//judge[i]：第i句话是真是假，真1假-1不清楚0  w[i]：第i局话是编号多少的的人说的
int judge[21], w[200];
//err：矛盾标记  nx：当前可能的罪犯
int err,  nx;
//name[i]：所有人名字（编号为1~m）  say[i]：所有人说的话  day[i]：所有星期几名字
string name[100], say[200];
string day[10] = {"0", "Today is Sunday.", "Today is Monday.",
                  "Today is Tuesday.", "Today is Wednesday.", "Today is Thursday.",
                  "Today is Friday.", "Today is Saturday.",
                 };
 
//sset函数标记一个人说话真假
void sset(int who, int x) {
	if (judge[who] == -x)
		err = 1; //如果一个人既说真话又说假话，则矛盾
	else
		judge[who] = x;
}
 
int main() {
	cin >> m >> n >> p;
	for (int i = 1; i <= m; i++) {
		cin >> name[i];
	}
	for (int i = 1; i <= p; i++) {
		string nm;
		cin >> nm; //输入说这句话人的名字
		nm.erase(nm.end() - 1); //删除nm中冒号，便于判断这句话编号多少的的人说的
		for (int j = 1; j <= m; j++) {
			if (name[j] == nm)
				w[i] = j;
		}
		getline(cin, say[i]);
		say[i].erase(say[i].begin()); //删除say[i]中的起始空格
	}
 
	for (int td = 1; td <= 7; td++) { //暴力枚举今天是星期几
		for (int px = 1; px <= m; px++) { //暴力枚举罪犯编号是几号
			err = 0; //清除标记
			memset(judge, 0, sizeof(judge)); //初始化为不清楚真假
			//依次判断每一句说的话
			for (int i = 1; i <= p; i++) {
				int who = w[i]; //说这句话人的编号
				//如果一个人是罪犯，并且说自己是罪犯，则说的就是真话，否则就是假话
				if (say[i] == "I am guilty.")
					sset(who, px == who ? 1 : -1);
				//如果一个人不是罪犯，并且说自己不是罪犯，则说的就是真话，否则就是假话
				if (say[i] == "I am not guilty.")
					sset(who, px != who ? 1 : -1);
				//如果一个人说今天是星期几，说对了就是真话，说错了就是假话
				for (int j = 1; j <= 7; j++) {
					if (say[i] == day[j])
						sset(who, j == td ? 1 : -1);
				}
				//如果一个人说其他人不是罪犯，说对了就是真话，说错了就是假话
				for (int j = 1; j <= m; j++) {
					if (say[i] == name[j] + " is guilty.")
						sset(who, j == px ? 1 : -1);
					if (say[i] == name[j] + " is not guilty.")
						sset(who, j != px ? 1 : -1);
				}
			}
			int cnt = 0; //说假话的人数
			int no = 0; //不清楚真假的的人数
			for (int i = 1; i <= m; i++) {
				if (judge[i] == -1) //假
					cnt++;
				if (judge[i] == 0) //不清楚
					no++;
			}
			//如果出现Impossible的情况，err = 1，出现矛盾
			//如果cnt<=n<=cnt+no,即假设合理
			if (!err && cnt <= n && cnt + no >= n) {
				if (nx && nx != px) { //如果出现了两个合理的罪犯
					cout << "Cannot Determine";
					return 0;
				} else {
					nx = px;
				}
			}
		}
	}
	if (!nx)
		cout << "Impossible";
	else
		cout << name[nx];
 
	return 0;
}