题目链接：点击打开链接
题目大意：一个矩形由n个小矩形组成，如今要给小矩形染色，可是颜料会向下滑，为了防止弄乱颜料，所以要先染上面的矩形，后然染以下的矩形。每一次改变颜色都要用一个新的刷子。问最小用多少刷子。
依照染色的条件。能够找到一个拓扑序列，拓扑序列中前面的要先染。后面的要后染，按拓扑的顺序dfs找出最少的刷字数。
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std ;
struct node{
int y1 , x1 , y2 , x2 , c ;
}p[20];
vector <int> vec[20] ;
int sta[20] , k ;
int in[20] , min1 , n ;
int vis[20] ;
int cmp(node a,node b) {
return a.y1 < b.y1 ;
}
void dfs(int c,int num,int ans) {
if( ans > min1 ) {
return ;
}
if( num == n ) {
min1 = ans ;
return ;
}
int i , j , l ;
for(i = 0 ; i < n ; i++) {
if( vis[i] || in[i] ) continue ;
if( p[i].c == c ) {
vis[i] = 1 ;
l = vec[i].size() ;
for(j = 0 ; j < l ; j++)
in[ vec[i][j] ]-- ;
sta[k++] = i ;
dfs(c,num+1,ans) ;
k-- ;
vis[i] = 0 ;
for(j = 0 ; j < l ; j++)
in[ vec[i][j] ]++ ;
}
else {
vis[i] = 1 ;
l = vec[i].size() ;
for(j = 0 ; j < l ; j++)
in[ vec[i][j] ]-- ;
sta[k++] = i ;
dfs(p[i].c,num+1,ans+1) ;
k-- ;
vis[i] = 0 ;
for(j = 0 ; j < l ; j++)
in[ vec[i][j] ]++ ;
}
}
}
int main() {
int t , i , j ;
scanf("%d", &t) ;
while( t-- ) {
scanf("%d", &n) ;
memset(in,0,sizeof(in)) ;
memset(vis,0,sizeof(vis)) ;
for(i = 0 ; i < n ; i++) vec[i].clear() ;
for(i = 0 ; i < n ; i++) {
scanf("%d %d %d %d %d", &p[i].y1, &p[i].x1, &p[i].y2, &p[i].x2, &p[i].c) ;
}
sort(p,p+n,cmp) ;
for(i = 0 ; i < n ; i++) {
for(j = i+1 ; j < n ; j++) {
if( p[i].y2 == p[j].y1 && !( p[j].x2 <= p[i].x1 || p[j].x1 >= p[i].x2 ) ) {
vec[i].push_back(j) ;
in[j]++ ;
}
}
}
min1 = 100 ;
for(i = 0 ; i < n ; i++) {
if( p[i].y1 ) break ;
dfs(p[i].c,0,0) ;
}
printf("%d
", min1+1) ;
}
return 0 ;
}