6163. 给定条件下构造矩阵——每日一难（phase2_day1）

6163. 给定条件下构造矩阵

给你一个 正 整数 k ，同时给你：

• 一个大小为 n 的二维整数数组 rowConditions ，其中 rowConditions[i] = [abovei, belowi]
• 和 一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [lefti,righti]

两个数组里的整数都是 1 到 k 之间的数字。

你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。

矩阵还需要满足以下条件：

• 对于所有 0 到 n - 1 之间的下标 i ，数字 abovei 所在的 行 必须在数字 belowi 所在行的上面。 对于所有 0 到
• m - 1 之间的下标 i ，数字 lefti 所在的 列 必须在数字 righti 所在列的左边。 返回满足上述要求的 任意
  矩阵。如果不存在答案，返回一个空的矩阵。

示例 1：

输入：k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]]
输出：[[3,0,0],[0,0,1],[0,2,0]] 解释：上图为一个符合所有条件的矩阵。

行要求如下：
数字 1 在第 1 行，数字 2 在第 2 行，1 在 2 的上面。
数字 3 在第 0 行，数字 2 在第 2 行，3 在 2 的上面。
列要求如下：
数字 2 在第 1 列，数字 1 在第 2 列，2 在 1 的左边。
数字 3 在第 0 列，数字 2 在第 1 列，3 在 2 的左边。 注意，可能有多种正确的答案。

示例 2：

输入：k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]]
输出：[]
解释：由前两个条件可以得到 3 在 1 的下面，但第三个条件是 3 在 1 的上面。
没有符合条件的矩阵存在，所以我们返回空矩阵。

提示：

• 2 <= k <= 400
• 1 <= rowConditions.length, colConditions.length <= 1e4
• rowConditions[i].length == colConditions[i].length == 2
• 1 <= abovei,
• belowi, lefti, righti <= k
• abovei != belowi lefti != righti

解析：

• 行与列分别处理
• 可以数字之间的关系看成图的关系，入度越小优先级越高
• 利用拓扑排序寻找优先级，如果有环就返回[]
• 分别找到行、列的优先级之后，按照行关系将所有元素放置在每一行的最后一列（随便一列都行），然后根据列关系调整在每一行的具体列。

代码：

class Solution {
public:
    bool topological_sort(vector<int>& degrees,vector<int>& res,unordered_map<int,unordered_set<int>>& ums,int k){
        queue<int> zeros;
        for(int i=1;i<=k;i++){
            if(degrees[i]==0)
                zeros.push(i);
        }
        while(!zeros.empty()){
            auto a = zeros.front();
            zeros.pop();
            res.push_back(a);
            for(auto b : ums[a]){
                degrees[b]--;
                if(degrees[b]==0)
                    zeros.push(b);
            }
        }
        // 如果有点度数不为0，则res中放不了k个元素，说明有环
        return res.size()==k;   
    }
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<vector<int>> ans(k,vector<int>(k,0));
        vector<vector<int>> ans2;
        vector<int> degrees(k+1,0);
        int m=rowConditions.size();
        int n=colConditions.size();
        // 图结构，用unordered_map存储，set去除相同的边
        unordered_map<int,unordered_set<int>> ums;
        for(auto a : rowConditions){
            if(ums[a[0]].find(a[1])==ums[a[0]].end()){
                ums[a[0]].insert(a[1]);
                degrees[a[1]]++;
            } 
        }
        
        vector<int> res;
        // 如果有环返回[]
        if(!topological_sort(degrees,res,ums,k)){
            return ans2;
        }
       
		// 处理列
        vector<int> degrees2(k+1,0);
        unordered_map<int,unordered_set<int>> ums2;
        for(auto a : colConditions){
            if(ums2[a[0]].find(a[1])==ums2[a[0]].end()){
                ums2[a[0]].insert(a[1]);
                degrees2[a[1]]++;
            } 
        }
        vector<int> res2;
        if(!topological_sort(degrees2,res2,ums2,k)){
            return ans2;
        }

		// 先处理行，同时间记住每一个数字所在行下标
        unordered_map<int,int> pmap;
        for(int i=0;i<k;i++){
            ans[i][k-1]=res[i];
            pmap[res[i]]=i;
        }
        // 根据列关系调整列的位置
        for(int i=0;i<k;i++){
            int a = pmap[res2[i]];
            ans[a][k-1] = 0;
            ans[a][i] = res2[i];
        }
        return ans;
    }
};
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71