⬅---------求赞(蒟蒻的第7个题解)
谢谢(●’◡’●)
题目描述
blabla
废话少说,入正题:
一眼看去妥妥的DFS
只是说,它的重点在于————
一块矩形若要涂色
那么它上面紧邻它的所有矩形都要先被涂过色
这个其实也好操作,有一个小小的坑点:
如果两个矩形上下紧邻,只是矩形A的右边界刚好触碰到矩形B的左边界(或反过来)
那么此时矩形A不需要先涂色,因为它俩没有实际上的交集
所以直接上代码吧 没压行,只有59行
#include<bits/stdc++.h>
using namespace std;
const int N=30;
struct node{
int x1,y1,x2,y2,c;
}a[N];
int n,ans=1e9;
bool st[N];
int have[N];
bool check(){
for(int i=1;i<=n;++i) if(!st[i]) return 0;
return 1;
}
bool check2(int i){
for(int j=1;j<=n;++j){
if(i==j || st[j]) continue;
if(!(a[i].y2<=a[j].y1 || a[i].y1>=a[j].y2) && a[i].x1==a[j].x2) return 0;
}
return 1;
}
void dfs(int num){
if(check()){
ans=min(ans,num);
return;
}
bool flag[N];
for(int i=1;i<=20;++i)
if(have[i]){
int h=have[i];
memset(flag,0,sizeof(flag));
for(int j=1;j<=n;++j){
if(a[j].c!=i || st[j] || !check2(j)) continue;
flag[j]=1;
st[j]=1;
have[i]--;
}
if(h==have[i]) continue;
dfs(num+1);
for(int j=1;j<=n;++j) if(flag[j]) st[j]=0,have[i]++;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2,&a[i].c);
have[a[i].c]++;
}
dfs(0);
printf("%d\n",ans);
return 0;
}