2022.03.23 华为机试Problem 3解题思路

问题简述：

M个面试官，会的语言各不相同

N个受试者，参与某种语言的面试

每个受试者需要2个面试官去面

每个面试官最多面k次

判断是否能够安排好面试？

输入：

4 6 4 (M,N,k)
java c py (面试官1会的3种语言)

py
c java
py
java （受试者前来面试的语言）
py
c
py
c
java

解决方案：dfs深度优先搜索

1.首先构建一个mat矩阵，存放面试官与受试者语言匹配关系，第m位面试官会第n位受试者的语言，则mat[m][n]=1，否则设为0

（这一步比较关键，如果能想到构建这种关系的话，应该就知道怎么解题了）

对上述情况例子，mat结果应为：

[1, 1, 1, 1, 1, 1]

[0, 1, 0, 1, 0, 0]

[1, 0, 1, 0, 1, 1]

[0, 1, 0, 1, 0, 0]

2.再初始化res矩阵，表示面试官与受试者是否要去匹配。在dfs中会对该矩阵的值进行更新：
若mat[m][n]=0,则由于不匹配，res[m][n]===0（恒为0）
否则res[m][n]可通过设置0/1表示不匹配/匹配。

例如第1行所有mat为1，则res第1行的每个格点，要么设为1表示组队面试，要么设为0表示不组队

3.dfs的深入方式：如果遇到mat格点为1，则设置res为0/1并进入下一格点，否则直接进入下一格点

dfs结束条件：格点越过右下角最后一格，此时需要判断本次遍历是否匹配成功

判断成功条件：条件1：各行不能大于k 条件2：各列必须等于2

4.上述例子的结果

    [1, 0, 1, 0, 1, 1]
    [0, 1, 0, 1, 0, 0]
    [1, 0, 1, 0, 1, 1]
    [0, 1, 0, 1, 0, 0]

注：

今晚做题时没做出来，前两题花了1.5h，剩半小时，这个题刚读完就想到这个思路了，

奈何感觉光写scanner就得花十多分钟，再加上脑子炸了，就放弃本题了。。。

考完冷静下来，花了快1h才写出来，还不确定对不对，测试用例反正是没问题。

写的代码太难看，我已经受不了了，不打算再改了，欢迎各位大佬补充或更改，或指出错误的地方！！！

代码+运行结果：

import java.util.*;

public class Main {
    //分别为面试官数、受试者数、面试最高次数
    static int M,N,k;
    //存放是否匹配的变量
    static boolean flag;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();
        k = sc.nextInt();
        sc.nextLine();
        //list存放第m位面试官会的语言，如list.get(0)存放第1位面试官的语言，String[]数组存放，长度不定
        ArrayList<String[]> list = new ArrayList<>();
        //mat矩阵存放面试官与受试者语言匹配关系，第m位面试官会第n位受试者的语言，则mat[m][n]=1，否则设为0
        int[][] mat = new int[M][N];
        //res为面试官与受试者是否要去匹配的矩阵。在递归中会对该矩阵的值进行更新
        // 若mat[m][n]=0,则由于不匹配，res[m][n]===0，
        // 否则res[m][n]可通过设置0/1表示 不匹配/匹配。
        int[][] res = new int[M][N];

        //读取面试官会的语言
        for(int i=0;i<M;i++){
            list.add(sc.nextLine().split(" "));
        }
        //下面代码边读取第i位受试者边填充第i列mat矩阵，遇到可以匹配的面试官就将值设为1
        for (int i = 0; i < N; i++) {
            String lg = sc.nextLine();  //读取i号受试者会的语言
            for(int j=0;j<M;j++){
                for(String str:list.get(j)){    //遍历当前面试官语言
                    if(str.equals(lg)){
                        mat[j][i] = 1;
                    }
                }
            }
        }
        //递归操作  递归方案为：遇到mat值为1的格子，对应res设置0或1，否则设置为0
        //当遍历过最后一个节点后，判断res是否满足  条件1：各行不能大于k  条件2：各列必须等于2
        //满足则输出该res矩阵并将flag设为true，否则返回。
        tracbrack(res,mat,0); //block指的是当前遍历到的格点位置，遍历方式：从左到右+1，到达最右端换行
        if(!flag) System.out.println(false);
    }
    public static void tracbrack(int[][] res, int[][] mat, int block){
        //结束条件，当block越过右下角最后一个格点时判断遍历结果
        if(block>=M*N){
            //判断各行和是否大于k
            for (int i = 0; i < M; i++) {
                int sum=0;
                for (int j = 0; j < N; j++) {
                    sum+=res[i][j];
                }
                if(sum>k) return;
            }
            //判断各列和是否等于2
            for (int j = 0; j < N; j++) {
                int sum=0;
                for (int i = 0; i < M; i++) {
                    sum+=res[i][j];
                }
                if(sum!=2) return;
            }
            //上述判断若无返回，说明本次遍历已成功，输出res并返回flag=true
            flag = true;
            System.out.println(true);
            for (int i = 0; i < M; i++) {
                System.out.println(Arrays.toString(res[i]));
            }
            return;
        }
        //计算格点下标，若M=4、N=6，则block=21对应(3,3)
        int x=block/N;
        int y=block%N;
        //如果当前mat=1，则对面试or不面试，即 res=0&nbs***bsp;1 分别进行两次递归
        if(mat[x][y]==1){
            res[x][y] = 0;
            tracbrack(res,mat,block+1);
            res[x][y] = 1;
            tracbrack(res,mat,block+1);
        }
        //如果当前mat=0，直接进入下一格
        else{
            tracbrack(res,mat,block+1);
        }
    }
}