1
7
0 0 2 2 1
0 2 1 6 2
2 0 4 2 1
1 2 4 4 2
1 4 3 6 1
4 0 6 4 1
3 4 6 6 2
#include<stdio.h>
#include<stdlib.h>
int data[100][100] = {0};
int zuo[16][5];
int z = 0;
int x = 0;
int y = 0;
int min = 15;
int cun[16] = {0};
int ip[15] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
int op[15];
int num = 0;
void DFS(int col,int step);
bool issafe(int c);
bool safe(int step,int i);
int main()
{
int n;
freopen("a.txt","r",stdin);
scanf("%d",&n);
for(int t = 0;t < n;t++)
{
scanf("%d",&z);
for(int r = 0;r < z;r++)
{
for(int s = 0;s < 5;s++)
{
scanf("%d",&zuo[r][s]);
if(zuo[r][2] > x)
{
x = zuo[r][2];
}
if(zuo[r][3] > y)
{
y = zuo[r][3];
}
}
}
DFS(0,0);
printf("%d
",min);
num = 0;
min = 15;
for(int f = 0;f < 17;f++)
{
op[f] = 0;
cun[f] = 0;
for(int l = 0;l < 6;l++)
{
zuo[f][l] = 0;
}
}
for(int p = 0;p <= x;p++)
{
for(int q = 0;q <= y;q++)
{
data[p][q] = 0;
}
}
}
return 0;
}
void DFS(int col,int step)
{
if(step == z)
{
if(num < min)
{
min = num;
}
return;
}
for(int i = 0;i < z;i++)
{
if(safe(step,i) && cun[i] == 0 && issafe(i))
{
cun[i] = 1;
op[step] = i;
for(int a = zuo[i][0];a < zuo[i][2];a++)
{
for(int b = zuo[i][1];b < zuo[i][3];b++)
{
data[a][b] = zuo[i][4];
}
}
if(col != zuo[i][4])
{
num++;
}
DFS(zuo[i][4],step + 1);
cun[i] = 0;
op[step] = 0;
for(int a = zuo[i][0];a < zuo[i][2];a++)
{
for(int b = zuo[i][1];b < zuo[i][3];b++)
{
data[a][b] = 0;
}
}
if(col != zuo[i][4])
{
num--;
}
}
}
}
bool issafe(int c)
{
bool ret = true;
for(int i = 0;i < zuo[c][0];i++)
{
for(int j = zuo[c][1];j < zuo[c][3];j++)
{
if(data[i][j] == 0)
{
ret = false;
return ret;
}
}
}
return ret;
}
bool safe(int step,int i)
{
bool ret = true;
for(int k = 0;k < step;k++)
{
if(i == op[k])
{
ret = false;
break;
}
}
return ret;
}