poj 1691
1777 ワード
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 15;
const int maxm = 20;
class node{
public:
int lx, ly, rx, ry, color;
};
int m, n;
node nn[maxn];
int mmin = 0x7fffffff;
int g[maxn][maxn];
int cnt[maxn];
bool visit[maxn];
int dfs(int dep, int sum, int color){
if(sum > mmin){
return 0;
}
if(dep == n){
mmin = min(mmin, sum);
return 0;
}
for(int i = 0; i < n; ++i){
if(!visit[i] && cnt[i] == 0){
visit[i] = true;
for(int j = 0; j < n; ++j){
if(g[i][j]){
--cnt[j];
}
}
if(color == nn[i].color){
dfs(dep + 1, sum, color);
}
else{
dfs(dep + 1, sum + 1, nn[i].color);
}
for(int j = 0; j < n; ++j){
if(g[i][j]){
++cnt[j];
}
}
visit[i] = false;
}
}
return 0;
}
bool isjudge(int i, int j){
if(nn[i].rx != nn[j].lx) return false;
if(nn[i].ry <= nn[j].ly) return false;
if(nn[i].ly >= nn[j].ry) return false;
return true;
}
int main(){
int tmplx, tmply, tmprx, tmpry, tmpcolor;
scanf("%d", &m);
int num = 0;
while(m--){
//cout << "m is " << m << endl;
memset(cnt, 0, sizeof(cnt));
memset(visit, 0, sizeof(visit));
memset(g, 0, sizeof(g));
num = 0;
mmin = 0x7fffffff;
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d%d%d%d%d", &nn[i].lx, &nn[i].ly, &nn[i].rx, &nn[i].ry, &nn[i].color);
}
//
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(isjudge(i, j)){
g[i][j] = 1;
cnt[j]++;
}
}
}
dfs(0, 0, 0);
printf("%d
",mmin);
}
return 0;
}