2021.11.11/dfs/平板排序
https://www.acwing.com/problem/content/1123/
对14个矩形进行拓扑排序，然后dfs搜索入度为0的点

#include<bits/stdc++.h>
using namespace std;

const int N = 20, M = 400;

int head[N], nxt[M], ver[M], tot = 1;
int ans = 100, n, counts;

struct p{
    int number, x1, y1, x2, y2;
} a[15];
//邻接表，加一条x -> y的边
void add(int x, int y){
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

void dfs(int cus, int color, int u, queue<int> q, vector<int> in_edge){
    if(cus >= ans) return;
    map<int, bool> mp;
    queue<int> tq;//保留与颜色color不一样的点
    //删除目前可以遍历到的与color相同的点，与color不同的放在tq中
    while(q.size()){
        int x = q.front(); q.pop();
        if(a[x].number == color){
            u--;//删掉点x，剩余点的个数就减一
            for(int i = head[x]; i; i = nxt[i]){//扫描x的所有出边
                int y = ver[i];
                if(--in_edge[y] == 0) q.push(y);//点y的入度减一，如果y的入度为0，加入队列
            }
        }
        else tq.push(x), mp[a[x].number] = 1;
    }

    if(u == 0){//没有剩下的点了，取出答案
        ans = min(ans, cus);
        return ;
    }

    for(auto [colors, v] : mp)
        dfs(cus + 1, colors, u, tq, in_edge);
}

int main(){
    vector<int> in_edge(15);
    map<int, bool> st;
    queue<int> q;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2 >> a[i].number;

    //当i块矩阵的下底 == j块矩阵的上边 并且 他们有交集的部分
    //加一条 i 到 j 的边
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(a[i].x2 == a[j].x1 && !(a[i].y2 <= a[j].y1 || a[i].y1 >= a[j].y2))
                add(i, j), in_edge[j]++;

    //扫描所有点，记录入度为0的点
    for(int i = 1; i <= n; i++)
        if(!in_edge[i]) q.push(i), st[a[i].number] = 1;
    for(auto [colors, v] : st)
        dfs(1, colors, n, q, in_edge);

    cout << ans;

    return 0;
}