本文涉及知识点

回溯 状态压缩 枚举

LeetCode 2151. 基于陈述统计最多好人数

游戏中存在两种角色：
好人：该角色只说真话。
坏人：该角色可能说真话，也可能说假话。
给你一个下标从 0 开始的二维整数数组 statements ，大小为 n x n ，表示 n 个玩家对彼此角色的陈述。具体来说，statements[i][j] 可以是下述值之一：

0 表示 i 的陈述认为 j 是 坏人 。
1 表示 i 的陈述认为 j 是 好人 。
2 表示 i 没有对 j 作出陈述。
另外，玩家不会对自己进行陈述。形式上，对所有 0 <= i < n ，都有 statements[i][i] = 2 。

根据这 n 个玩家的陈述，返回可以认为是 好人 的 最大 数目。

示例 1：

输入：statements = [[2,1,2],[1,2,2],[2,0,2]]
输出：2
解释：每个人都做一条陈述。

• 0 认为 1 是好人。
• 1 认为 0 是好人。
• 2 认为 1 是坏人。
  以 2 为突破点。
• 假设 2 是一个好人：
  • 基于 2 的陈述，1 是坏人。
  • 那么可以确认 1 是坏人，2 是好人。
  • 基于 1 的陈述，由于 1 是坏人，那么他在陈述时可能：
    • 说真话。在这种情况下会出现矛盾，所以假设无效。
    • 说假话。在这种情况下，0 也是坏人并且在陈述时说假话。
  • 在认为 2 是好人的情况下，这组玩家中只有一个好人。
• 假设 2 是一个坏人：
  • 基于 2 的陈述，由于 2 是坏人，那么他在陈述时可能：
    • 说真话。在这种情况下，0 和 1 都是坏人。
      • 在认为 2 是坏人但说真话的情况下，这组玩家中没有一个好人。
    • 说假话。在这种情况下，1 是好人。
      • 由于 1 是好人，0 也是好人。
      • 在认为 2 是坏人且说假话的情况下，这组玩家中有两个好人。
        在最佳情况下，至多有两个好人，所以返回 2 。
        注意，能得到此结论的方法不止一种。
        示例 2：
        

输入：statements = [[2,0],[0,2]]
输出：1
解释：每个人都做一条陈述。

• 0 认为 1 是坏人。
• 1 认为 0 是坏人。
  以 0 为突破点。
• 假设 0 是一个好人：
  • 基于与 0 的陈述，1 是坏人并说假话。
  • 在认为 0 是好人的情况下，这组玩家中只有一个好人。
• 假设 0 是一个坏人：
  • 基于 0 的陈述，由于 0 是坏人，那么他在陈述时可能：
    • 说真话。在这种情况下，0 和 1 都是坏人。
      • 在认为 0 是坏人但说真话的情况下，这组玩家中没有一个好人。
    • 说假话。在这种情况下，1 是好人。
      • 在认为 0 是坏人且说假话的情况下，这组玩家中只有一个好人。
        在最佳情况下，至多有一个好人，所以返回 1 。
        注意，能得到此结论的方法不止一种。

提示：

n == statements.length == statements[i].length
2 <= n <= 15
statements[i][j] 的值为 0、1 或 2
statements[i][i] == 2

回溯

回溯层次leve：n
子回溯：第leve个人，分别为是好人，和坏人。
状态： 层次leve，vGood 记录结果，vGood [i]为0 表示坏人，为1表示好人，为2表示未知。
修改状态：
如果leve好人：
vGood[leve]不为0，statements[i]和vGood不矛盾。vGood[leve]=1 通过statements[i]更新vGood。
如果leve是坏人：
vGood[leve]不为1。 vGood[leve] 设置为1。
状态恢复：
修改前tmp = vGood，恢复时vGood =tmp
初始状态：vGood全为2，leve为0。

枚举、状态压缩

iMask记录好人、坏人状态。 iMask&i 表示第i个人是否是好人。如果不矛盾更新返回值。

回溯代码

class Solution {
public:
	int maximumGood(vector<vector<int>>& statements) {
		int iRet = 0;
		vector<int> vGood(statements.size(), 2);
		function<void(int)> BackTrack = [&](int leve) {
			if (statements.size() == leve) {
				iRet=max(iRet, (int)std::count(vGood.begin(), vGood.end(),1));
				return;
			}			
			if (1 != vGood[leve]) {
				auto tmp = vGood;
				vGood[leve] = 0;
				BackTrack(leve + 1);
				vGood = tmp;
			}
			if ((0 != vGood[leve])&& Is(vGood, statements[leve]))
			{
				auto tmp = vGood;
				vGood[leve] = 1;
				for (int i = 0; i < vGood.size(); i++) {
					if (2 == statements[leve][i]) { continue; }
					vGood[i] = statements[leve][i];
				}
				BackTrack(leve + 1);
				vGood = tmp;
			}
		};
		BackTrack(0);
		return iRet;
	}
	bool Is(const vector<int>& v1, const vector<int>& v2)	{
		for (int i = 0; i < v1.size(); i++) {
			if (1 == v1[i] + v2[i]) { return false; }
		}
		return true;
	}
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。