思路是用SPFA求“所有均未涂色的状态”节点到“所有均涂色的状态”节点的最短路。

A状态到B状态有一条边，是在已涂了状态A的情况下，再尽可能多的涂了某一种颜色之后，变成了状态B。

因为是贪心的涂色，且有拓扑序的限制，所以考虑用哈希表存状态对应的最小涂色次数。

下不了测试数据啊，不知道哪里错了，求大佬给看看（或者偷偷分享一下测试数据7）QAQ

#include<iostream>
#include<unordered_map> 
#include<queue> 
using namespace std;
const int color = 20;
struct block { //矩形
	int x1, y1;
	int x2, y2;
	int color; 
}bl[16];
int fa[16]; //每个矩形需要先涂的其他矩形(状压）
unordered_map<int, int> dp; //已涂状态（状压）的最少涂色次数
unordered_map<int, bool> vis;
queue<int> Q;  //最短路队列
int main() {
	int n ;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> bl[i].y1 >> bl[i].x1 >> bl[i].y2 >> bl[i].x2 >> bl[i].color;
	} 
	for (int i = 0; i < n; i++) { 
		for (int j = 0; j < n; j++) if (i != j && bl[i].y1 == bl[j].y2 && !(bl[i].x1 >= bl[j].x2 || bl[i].x2 <= bl[j].x1)) { 
			//如果矩形i的上面的边的y等于矩形j下面的边的y值。且相交（即矩形的x左端点不大于另外一个矩形的x右端点）
			fa[i] = fa[i] | (1 << j);
		}
	}
	Q.push(0); //从起始点即起始状态求最短路
	vis[0] = true;
	while (!Q.empty()) { //SPFA
		int status = Q.front(); 
		vis[status] = false;
		Q.pop();
		int i = 0;
		for (int color = 1; color <= 20; color++) { //枚举新涂的下一个颜色
			int newStatus = status; bool updated = true;
			while (updated) { 
				updated = false;
				int status2 = newStatus;
				for (int i = 0; i < n; i++) if (bl[i].color == color && (fa[i] & status2) == fa[i]) { //枚举所有颜色是目标颜色的方格，且父节点状态也都已经被涂
					status2 = status2 | (1 << i); //把i节点也涂上
				}
				if (newStatus != status2) { //循环直到不能再涂更多的节点
					newStatus = status2;
					updated = true;
				}
			}
			if (dp.find(newStatus) == dp.end() || dp[newStatus] >dp[status]+1) { //SFPA的更新
				dp[newStatus] = dp[status] + 1;
				if (vis.find(newStatus) == vis.end() || !vis[newStatus]) {
					Q.push(newStatus); 
					vis[newStatus] = true;
				}
			}
		}
	}
	cout << dp[(1<<n)-1];
	return 0;
}