同样是搜索经典题。
优化并不多，只需在当前步数已经大于目前答案时剪枝就可以了。
此题重点在于如何判断第k个矩形能不能选。
设矩形i的左上坐标为i(squ[i].upx,squ[i].upy),右下角坐标为i(squ[i].dox,squ[i].doy)。则判断k号矩形可以涂的条件为：
if(!vis[i]&&(squ[k].upy==squ[i].doy)&&((squ[i].upx>=squ[k].upx&&squ[i].upx<=squ[k].dox)||(squ[i].dox>=squ[k].upx&&squ[i].dox<=squ[k].dox)))
即：如果i号矩形没有涂色且i号矩形为紧靠k上方的矩形，就不可以涂色。
重点来解释一下如何判定i号矩形为紧靠k矩形上方的矩形。
第一，如果i号矩形为紧靠k矩形上方的矩形，那么i号矩形右下角的纵坐标一定等于k号矩形左上角的纵坐标，这个很好理解，对应判断条件中的(squ[k].upy==squ[i].doy)。
第二，如何判断[squ[i].upx,squ[i].dox]和[squ[k].upx,squ[i].dox]有没有交集呢？只需要看是否有一个端点位于线段中即可，读者可以结合下图理解：
下面正常深搜即可。
下面给出参考代码：
1 #include<iostream> 2 #include<cstdio> 3 #define N 205 4 using namespace std; 5 struct node 6 { 7 int upx,upy,dox,doy,col; 8 }squ[N]; 9 int n,ans; 10 bool vis[N]; 11 bool check(int k) 12 { 13 for(int i=1;i<=n;i++) 14 { 15 if(!vis[i]&&(squ[k].upy==squ[i].doy)&&((squ[i].upx>=squ[k].upx&&squ[i].upx<=squ[k].dox)||(squ[i].dox>=squ[k].upx&&squ[i].dox<=squ[k].dox)))return 0; 16 } 17 return 1; 18 } 19 void dfs(int step,int node,int col) 20 { 21 if(step>=ans)return; 22 if(node==n)ans=step; 23 for(int i=1;i<=n;i++) 24 { 25 if(!vis[i]&&check(i)) 26 { 27 if(squ[i].col==col) 28 { 29 vis[i]=1; 30 dfs(step,node+1,col); 31 vis[i]=0; 32 } 33 else 34 { 35 vis[i]=1; 36 dfs(step+1,node+1,squ[i].col); 37 vis[i]=0; 38 } 39 } 40 } 41 } 42 int main() 43 { 44 cin>>n; 45 ans=n; 46 for(int i=1;i<=n;i++) 47 { 48 cin>>squ[i].upy>>squ[i].upx>>squ[i].doy>>squ[i].dox>>squ[i].col; 49 } 50 dfs(0,0,-1); 51 cout<<ans<<endl; 52 }