本文主要是介绍poj1691--Painting A Board(拓扑+dfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：一个矩形由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\n", min1+1) ;}return 0 ;
}
这篇关于poj1691--Painting A Board(拓扑+dfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
