【021·未解】1947. 最大兼容性评分和【暴力回溯】

有一份由 n 个问题组成的调查问卷，每个问题的答案要么是 0（no，否），要么是 1（yes，是）。 这份调查问卷被分发给 m 名学生和 m
名导师，学生和导师的编号都是从 0 到 m - 1 。学生的答案用一个二维整数数组 students 表示，其中 students[i]
是一个整数数组，包含第 i 名学生对调查问卷给出的答案（下标从 0 开始）。导师的答案用一个二维整数数组 mentors 表示，其中
mentors[j] 是一个整数数组，包含第 j 名导师对调查问卷给出的答案（下标从 0 开始）。 每个学生都会被分配给 一名
导师，而每位导师也会分配到 一名 学生。配对的学生与导师之间的兼容性评分等于学生和导师答案相同的次数。 例如，学生答案为[1, 0, 1]
而导师答案为 [0, 0, 1] ，那么他们的兼容性评分为 2 ，因为只有第二个和第三个答案相同。 请你找出最优的学生与导师的配对方案，以
最大程度上 提高 兼容性评分和 。 给你 students 和 mentors ，返回可以得到的 最大兼容性评分和 。

https://leetcode.cn/problems/maximum-compatibility-score-sum/description/

1. 预处理学生老师匹配得分，转化为求 矩阵最大值（行与列不相同）
2. 回溯学习好文：https://www.jianshu.com/p/412a72786e5a
3. 暴力回溯：for循环之前，确定判断条件，结束分支循环。for循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

/*
 * Copyright (c) Huawei Technologies Co., Ltd. 2023-2023. All rights reserved.
 */

package com.huawei.prac;

public class Solution4th {

    static int maxCount;

    public static void main(String[] args) {
        int[][] students = {{1, 1, 0}, {1, 0, 1}, {0, 0, 1}};
        int[][] mentors = {{1, 0, 0}, {0, 0, 1}, {1, 1, 0}};
        System.out.println(maxCompatibilitySum(students, mentors));
    }

    /**
     * 1947【未解】. 最大兼容性评分和
     *
     * @param students 学生答题情况数组
     * @param mentors 导师答题情况数组
     * @return 最大兼容性评分和
     */
    public static int maxCompatibilitySum(int[][] students, int[][] mentors) {
        maxCount = 0;
        // markArr[i][j]为学生i分配给老师j的得分
        int[][] markArr = new int[students.length][students.length];
        for (int i = 0; i < students.length; i++) {
            for (int j = 0; j < students.length; j++) {
                for (int k = 0; k < students[0].length; k++) {
                    markArr[i][j] += students[i][k] == mentors[j][k] ? 1 : 0;
                }
            }
        }

        // 转化为求 矩阵最大值（行与列不相同）
        backTrace(markArr, new boolean[markArr.length], 0, 0);
        return maxCount;
    }

    private static void backTrace(int[][] markArr, boolean[] visited, int index, int curScore) {
        if (index >= markArr.length) {
            maxCount = Math.max(maxCount, curScore);
            return;
        }

        for (int i = 0; i < markArr.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            backTrace(markArr, visited, index + 1, curScore + markArr[i][index]);
            visited[i] = false;
        }
    }
}