“This is the fifth day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Day 27 2021.1.23

# Count the maximum number of good people based on statements

• Leetcode: leetcode-cn.com/problems/ma…
• Difficulty: difficulty
• Methods: DFS (depth-first search), simulation

## The title

• There are two types of characters:
• Good guy: The character only tells the truth.
• Bad guy: This character may or may not tell the truth.
• You are given a two-dimensional array of integer statements with subscripts starting at 0, size n x n, which represent the statements made by n players about each other’s characters. Specifically, statements[I][j] can be one of the following values:
• 0 means I’s statement thinks J is bad.
• 1 represents I’s statement that J is a good person.
• 2 means that I has not made a statement to J.
• In addition, players don’t make statements to themselves. Formally, there are statements[I][I] = 2 for all 0 <= I < n.

• Based on these n player statements, return the maximum number of people that can be considered good people.

## The sample

• Example 1

(For details on the topic, it is too long, please refer to the original leetcode)

• Example 2

(For details on the topic, it is too long, please refer to the original leetcode)

## prompt

• `n == statements.length == statements[i].length`
• `2 <= n <= 15`
• `Statements [I][j] have a value of 0, 1 or 2`
• `statements[i][i] == 2`

## solution

• use`dfs`simulation
``````/ * * *@param {number[][]} statements
* @return {number}* /

var maximumGood = function(statements) {
/ / define DFS
let ans = 0;
// The definition records each situation, each person's condition
let flag = [];
let len = statements.length;
let jump = false;

// Count the number of 1s
let numOne = 0;
function dfs(n, t) {
if (n == len) {
// If there is no contradiction, record it
// 1: good guy. 0: bad guy
numOne = 0;
for (let i = 0; i < n; i++) {
// console.log('i',i,flag);
if (flag[i] == 1) {
numOne++;
// console.log('flag',flag[i]);
// If flag is 1, good people need to be compared
// I -> < span style = "max-width: 100%; clear: both; min-height: 1em
for(let j = 0; j < n; j++) {
// indicates j -> 1
if (i == j || statements[i][j] == 2) {
continue;
}
if(flag[j] ! = statements[i][j]) {// jump = true;
// numOne = 0;
// break;
return; }}}// if (jump){
// jump = false;
// break;
// }
}

ans = Math.max(ans,numOne);
// console.log(' get results ',ans);
return;
}

flag[n] = t;
// If not, continue recursing
dfs(n + 1.0);
dfs(n + 1.1);
}

dfs(0.0);
dfs(0.1);
return ans;
};
Copy the code``````