侦探推理

先上链接,各位可以先去尝试一下:P1039 侦探推理 - 洛谷

这是一道难度标记为: 提高+/省选- 的题目,但个人感觉处理好字符串后并不难。

题目描述

明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中,于是他召集了一群同学玩推理游戏。游戏的内容是这样的,明明的同学们先商量好由其中的一个人充当罪犯(在明明不知情的情况下),明明的任务就是找出这个罪犯。接着,明明逐个询问每一个同学,被询问者可能会说:

证词.png

证词中出现的其他话,都不列入逻辑推理的内容。

明明所知道的是,他的同学中有NN个人始终说假话,其余的人始终说真。

现在,明明需要你帮助他从他同学的话中推断出谁是真正的凶手,请记住,凶手只有一个!

解题思路

刚刚拿到题就发现证词内容可能会比较难处理!(这里说的CPP,其他语言会好很多)

最初想到:枚举出每个玩家是囚犯的可能性,然后再检查是否合理。

尝试以后,发现这种方法只能处理指认罪犯和证明谁不是罪犯,一到说日期相关的时候就会出问题。

后来,想到一种更好的方法,只需在基础上增加日期的枚举,既然无法确定日期,就假设一个日期。

输入格式

由于换行符问题,直接使用 getline 函数无法取得准确的证词!

请将以下代码放置在输入前(本地测试不需要):

char ch=getchar();
while(ch==10)ch=getchar();getchar();

以及在取得输入数据后使用以下方法处理证词:

talks[i].erase(talks[i].end() - 1);

使用以上方法即可在洛谷正常运行代码(否则全WA!!)

语法解析

我的想法是将语法解析为一个 map<string, int> 它会存放一条证词的状态信息。

typedef map<string, int> statf; // 单个证词的各种状态信息
vector<statf> cons; // 这里将存放所有证词的信息

statf tmp;
tmp["player"] = userid; // 证词发布者的 ID
tmp["ensure"] = -1; // 指认的目标ID (-1 代表证词未指认)
tmp["ensure"] = -1; // 证明谁不是罪犯的目标ID (-1 代表证词未证明)
tmp["date"] = 1; // 证词说明的日期 (-1 代表未说明日期)

cons.push_back(tmp);

上方是我存放证词信息的方法(个人感觉还是比较通俗易懂的)

// 整体的语法转换
void grammerAnalysis(string talk)
{
    string name = "";   // 证词发表人名
    int talk_start = 0; // 证词正文起点

    for (int i = 0; i < talk.length(); i++)
    {
        // 识别证词发表人的名字 (到 : 结束)
        if (talk[i] == ':' && talk[i + 1] == ' ')
        {
            talk_start = i + 2; // 取得证词正文起点
            break;
        }
        name += talk[i];
    }

    // 取得发表人 ID号
    int uid = -1;
    for (int i = 0; i < m; i++)
    {
        if (players[i] == name)
        {
            uid = i;
            break;
        }
    }
    if (uid == -1)
    {
        return; //人物不存在,结束后续操作
    }

    string content = "";

    // 取得证词全文
    for (int i = talk_start; i <= talk.length(); i++)
    {
        if (talk[i] != 0)
        {
            content += talk[i];
        }
    }

    map<string, int> tmp;
    tmp["player"] = uid;
    int anay = 0;

    // 识别对自己提供的证词
    // cout << (int)content[content.length() - 1] << endl;
    if (content == "I am guilty.")
    {
        tmp["ensure"] = uid;
        tmp["denial"] = -1;
        tmp["date"] = -1;
        anay = 1;
    }
    else if (content == "I am not guilty.")
    {
        tmp["ensure"] = -1;
        tmp["denial"] = uid;
        tmp["date"] = -1;
        anay = 1;
    }
    else
    {
        if (week.find(content) != week.end())
        {
            tmp["ensure"] = -1;
            tmp["denial"] = -1;
            tmp["date"] = week[content];
            anay = 1;
        }
        else
        {
            // 解析是否指正他人
            int target = -1;
            bool forname = true;
            string anct = "";
            string tnam = "";

            for (int i = 0; i < content.length(); i++)
            {
                if (forname)
                {
                    if (content[i] == ' ')
                    {
                        for (int i = 0; i < m; i++)
                        {
                            if (players[i] == tnam)
                            {
                                target = i;
                                forname = false;
                                break;
                            }
                        }
                    }
                    else
                    {
                        tnam += content[i];
                    }
                }
                else
                {
                    anct += content[i];
                }
            }

            if (target != -1)
            {
                if (anct == "is guilty.")
                {
                    tmp["ensure"] = target;
                    tmp["denial"] = -1;
                    tmp["date"] = -1;
                    anay = 1;
                }
                else if (anct == "is not guilty.")
                {
                    tmp["ensure"] = -1;
                    tmp["denial"] = target;
                    tmp["date"] = -1;
                    anay = 1;
                }
            }
        }
    }

    // 如果为合法证词则将数据存入
    if (anay == 1)
    {
        cons.push_back(tmp);
    }
}

上面是个人的语法解析代码(还可进行优化)

PS:这里的日期信息初始化需要先调用

map<string, int> week; // 日期对应表

// 初始化日期信息
void initData()
{
    week["Today is Monday."] = 1;
    week["Today is Tuesday."] = 2;
    week["Today is Wednesday."] = 3;
    week["Today is Thursday."] = 4;
    week["Today is Friday."] = 5;
    week["Today is Saturday."] = 6;
    week["Today is Sunday."] = 7;
}

这里的语法转换函数我是在每输入一个证词时就对证词处理一次,可以减少循环的使用。

判断结果

为了判断结果,需要使用三层的循环:

  1. 玩家遍历(假设每个人是罪犯)
  2. 日期遍历(周一到周天的日期)
  3. 证词遍历(依次处理每一条证词)

博主在枚举每一天情况处初始化了两个变量:[整数数组]uinfo[布尔类型]error

这两个变量分别存放了用户的信息(未知、诚实、撒谎)和 是否出现冲突

在进入第三次遍历(证词遍历)时,就需要对证词的属性进行判定(指认他人,否认他人,日期声明)

这里我们只需要进行简单的对比就可以知道此人是否撒谎:

// 判断日期是否和今天日期相同
if(talk["date"] == day){}

// 判断指认的人是不是假设的罪犯
if (talk["ensure"] == who){}

// 判断否认的人是不是假设的罪犯
if (talk["denial"] != who){}

// 通过上面三种简单的方法就能判断一个人是否撒谎!

你以为简单的三次判断就结束了?其实还有一个很关键的点被忽略了!

我们现在做的一切都是假设,假设一定会存在不合理!

如果直接给一个人下定义他是否撒谎,那将会大错特错!我们需要检查是否出现了不合理!

给一个案例自己体会一下:

3 1 4
Sam
Jack
Kevin
Sam: Today is Sunday.
Jack: Today is Friday.
Sam: I am guilty.
Kevin: I am not guilty.

如果不检查合理性,当我们来到假设:Jack是罪犯且今天是Sunday时,一个问题就会出现。

Sam说是Sunday[没有问题],但他又说自己是罪犯!(这里就发生冲突了)

你说Sam撒谎了,但Sunday确实没毛病。你说他没撒谎,但他也不是罪犯啊!

解决方法其实很简单:判断是否撒谎后,再和此人之前的信息对比,如果这次撒谎了但上次没有,则说明这次假设本身就有问题,直接把它跳过就行了(这就是 error 变量的用处)

证词矛盾可过滤掉百分之九十的错误假设!另外一种需要限制的就是撒谎人数,当撒谎人数超过案例给的撒谎人数,这条假设也可以直接跳过了。

最后,没有 矛盾和超出人数 就说明这条假设已经成立了!可以确定为罪犯了。

注意事项

本题有一个测试样例如下:

2 2 4
HELLO
GUILTY
HELLO: What is your name?
GUILTY: I am GUILTY.
GUILTY: Are you guilty?
HELLO: I am not guilty.

本样例有两个玩家,且有两个人说谎。

但可以看到 GUILTY 一直在说废话(无效证词),而真正撒谎但只有 HELLO 一人!

经过程序分析,GUILTY 的类型为0(未知),HELLO 则为2(撒谎)

既然不知道 GUILTY 有没有撒谎,且撒谎人数差一个,就可以把不确定的人定义为撒谎的人。

不知道撒谎没,就把他当作撒了谎的人!

特殊情况

本题除了正常输出罪犯的名字外,还有可能输出“Cannot Determine”“Impossible”

  • Cannot Determine: 不止一个人是罪犯,就是在程序依次假设玩家是罪犯时,有多条假设是成立的。
  • Impossible: 没有人可能是罪犯,也就是在程序枚举出所有情况后,没有一种假设是成立的。

为了准确识别这两种可能性,我使用了一个 int 变量 offender 储存确定的罪犯信息。

这个变量默认值为 -1 即代表目前没有任何人可被确定为罪犯。

完整代码

本文主要介绍了本题的思路,如果你想要完整代码需要先进行评论!

此处内容需要评论回复后(审核通过)方可阅读。

Last modification:June 18th, 2020 at 01:06 pm
如果觉得我的文章对你有用,请随意赞赏