# include <iostream.h>
# include <stdlib.h>
# include <memory.h>
const int N=16;

struct Rectangle{
	int r1,c1;
	int r2,c2;
	int color;
	bool isPainted;
};

Rectangle rec[N];//describe the rectangles

bool isImediateUp[N][N];//if isImediateUp[i][j]=true then i is imediately up on j
int recsUp[N];

int recnums;
int brushes;//the times of change brushes
int min;//the minimum times

void paintrec(int c);
void Paintsearch();

void main(){
	int cases;
	int i,j;	

	cin>>cases;
	while (cases--){
		//load in data
		cin>>recnums;
		for (i=0;i<recnums;i++){
			cin>>rec[i].r1>>rec[i].c1>>rec[i].r2>>rec[i].c2>>rec[i].color;
			rec[i].isPainted=false;
		}
		
		//initial sets
		memset(recsUp,0,sizeof(int));
		memset(isImediateUp,0,sizeof(bool));
		
		//describe the structure of the recs(especially the up-relation)
		for (i=0;i<recnums;i++){
			for (j=0;j<recnums;j++){
				if (i==j)	continue;
				//1.the top ends the bottom//2.the left and right side both within the edge
				if (rec[i].r2==rec[j].r1 && !(rec[i].c2<=rec[j].c1 || rec[i].c1>=rec[j].c2)){
					isImediateUp[i][j]=true;//i is immediately up on j
					recsUp[j]++;//recs immediately upon j
				}
			}
		}
		//calculate the paint times
		min=recnums;
		brushes=0;
		Paintsearch();
		cout<<min<<endl;
	}
}


void Paintsearch(){
	int i,j,k;
	bool isover=true;
	bool temp_isPainted[N];
	bool temp_isImediateUp[N][N];
	int temp_recsUp[N];	

	for (i=0;i<recnums;i++){
		if (rec[i].isPainted==false)	{isover=false;break;}
	}
	if (isover==true){//ending condition
		if (brushes<min)	min=brushes;
		return;
	}

	for (i=0;i<recnums;i++){//search which color can be painted now
		if (rec[i].isPainted == true)	continue;
		if (recsUp[i] != 0)				continue;

		for (j=0;j<recnums;j++)	{
			temp_isPainted[j]=rec[j].isPainted;
			temp_recsUp[j]=recsUp[j];
			for (k=0;k<recnums;k++)	temp_isImediateUp[j][k]=isImediateUp[j][k];
		}

		paintrec(rec[i].color);//paint the color
		brushes++;

		Paintsearch();

		brushes--;
		for (j=0;j<recnums;j++){
			rec[j].isPainted=temp_isPainted[j];
			recsUp[j]=temp_recsUp[j];
			for (k=0;k<recnums;k++)	isImediateUp[j][k]=temp_isImediateUp[j][k];
		}
	}
}


void paintrec(int c){//use brush with c color to paint all recs now that can be painted
	int i,j;
	for (i=0;i<recnums;i++){
		if (rec[i].color != c)		continue;
		if (recsUp[i] != 0)			continue;
		if (rec[i].isPainted==true)	continue;
		//paint the rec
		rec[i].isPainted=true;
		//substract the rectangles pressed by rec_i
		for (j=0;j<recnums;j++){
			if (i==j)	continue;
			if (isImediateUp[i][j]==true){
				isImediateUp[i][j]=false;
				recsUp[j]--;
			}
		}
	}
}

• 我自己解决了，感觉真好^_^ (2969) testjoan 2006-03-25 20:07:26