喷漆机器人问题
时间： 1ms 内存：64M
描述：
F大学开发出一种喷漆机器人Rob，能用指定颜色给一块矩形材料喷漆。Rob每次拿起一种颜色的喷枪，为指定颜色的小矩形区域喷漆。喷漆工艺要求，一个小矩形区域只能在所有紧靠它上方的矩形区域都喷过漆后，才能开始喷漆，且小矩形区域开始喷漆后必须一次性喷完，不能只喷一部分。为Rob编写一个自动喷漆程序，使Rob拿起喷枪的次数最少。
对于给定的矩形区域和指定的颜色，计算Rob拿起喷枪的最少次数。
输入：
输入数据的第一行有1 个正整数n，1≤n≤16，表示小矩形的个数。大矩形坐标系如图所示，左上角点的坐标为(0,0)。颜色编号为正整数。接下来的n行，每行用5 个整数y1,x1,y2,x2,c来表示一个矩形。(x1,y1)和(x2,y2)分别表示小矩形的左上角点坐标和右下角点坐标，c表示小矩形的颜色。
输出：
将计算出的Rob拿起喷枪的最少次数输出。
示例输入：
7
0 0 2 2 1
0 2 1 6 2
2 0 4 2 1
1 2 4 3 2
1 3 3 6 1
4 0 6 3 1
3 3 6 6 2示例输出：
3提示：
参考答案（内存最优[1092]）：
#include <stdio.h>
#include <stdlib.h>
int n;
int current_color=-999999999;
int numofgun;
struct X
{
int x1,y1,x2,y2,c;
int father[20];
int flag;
int sum;
} rec[20];
int minis=9999999;
void update(int x)
{
int i,j;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
if(rec[i].father[j]==x)
rec[i].sum--;
}
}
void downdate(int x)
{
int i,j;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
if(rec[i].father[j]==x)
rec[i].sum++;
}
}
void dfs(int x)
{
int i,j;
if(x==n)
{
if(numofgun<minis)
minis=numofgun;
return;
}
for(i=1; i<=n; i++)
{
if(rec[i].sum==0&&rec[i].flag==0)
{
if(rec[i].c!=current_color)
{
j=current_color;
numofgun++;
current_color=rec[i].c;
rec[i].flag=1;
update(i);
dfs(x+1);
downdate(i);
numofgun--;
current_color=j;
rec[i].flag=0;
}
else
{
rec[i].flag=1;
update(i);
dfs(x+1);
downdate(i);
rec[i].flag=0;
}
}
}
}
int main()
{
scanf("%d",&n);
int i,j;
for(i=1; i<=n; i++)
{
scanf("%d%d%d%d%d",&rec[i].y1,&rec[i].x1,&rec[i].y2,&rec[i].x2,&rec[i].c);
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if((rec[i].y1==rec[j].y2)&&((rec[i].x2>rec[j].x1&&rec[i].x2<=rec[j].x2)||(rec[i].x1>=rec[j].x1&&rec[i].x1<rec[j].x2)||(rec[j].x1>=rec[i].x1&&rec[j].x1<rec[i].x2)||(rec[j].x2>rec[j].x1&&rec[j].x2<rec[j].x2)))
{
rec[i].sum++;
rec[i].father[rec[i].sum]=j;
}
}
}
dfs(0);
printf("%d",minis);
return 0;
}
参考答案（时间最优[0]）：
#include<iostream>
#include<algorithm>
#include<memory.h>
#include<cstdio>
using namespace std;
struct point
{
int x1,y1;
int x2,y2;
int color;
int father[20];
int sum;
int flag;
}p[20];
int n;
int sum=0;
int result=99999999;
void Init()
{
cin>>n;
for(int i=1;i<n+1;i++)
{
memset(p[i].father,0,sizeof(p[i].father));
p[i].sum=0;
p[i].flag=0;
cin>>p[i].y1>>p[i].x1;
cin>>p[i].y2>>p[i].x2;
cin>>p[i].color;
}
}
int Judge()
{
for(int i=1;i<n+1;i++)
{
for(int j=1;j<n+1;j++)
{
if(i==j)
{
continue;
}
else
{
if(p[i].y1==p[j].y2)
{
if((p[i].x1>=p[j].x1&&p[i].x1<=p[j].x2)||(p[i].x2>=p[j].x1&&p[i].x2<=p[j].x2)||(p[i].x1<=p[j].x1&&p[i].x2>=p[j].x2))
{
p[i].father[j]=1;
p[i].sum++;
}
}
}
}
}
}
int Update(int num)
{
for(int i=1;i<n+1;i++)
{
if(p[i].father[num]==1)
{
p[i].sum--;
}
}
}
void Fupdate(int num)
{
for(int i=1;i<n+1;i++)
{
if(p[i].father[num]==1)
{
p[i].sum++;
}
}
}
void dfs(int num,int color,int cnt)
{
if(sum==n)
{
result=min(result,cnt);
return;
}
int flag=0;
for(int i=1;i<n+1;i++)
{
if(flag==1)
{
break;
}
if(p[i].sum==0&&p[i].flag==0&&p[i].color==color)
{
flag=1;
p[i].flag=1;
Update(i);
sum++;
dfs(i,p[i].color,cnt);
Fupdate(i);
sum--;
p[i].flag=0;
}
}
if(flag==0)
{
for(int i=1;i<n+1;i++)
{
if(p[i].sum==0&&p[i].flag==0)
{
p[i].flag=1;
Update(i);
sum++;
dfs(i,p[i].color,cnt+1);
Fupdate(i);
sum--;
p[i].flag=0;
}
}
}
}
int main(){
Init();
Judge();
for(int i=1;i<n+1;i++)
{
if(p[i].sum==0&&p[i].flag==0)
{
p[i].flag=1;
Update(i);
sum++;
dfs(i,p[i].color,1);
Fupdate(i);
sum--;
p[i].flag=0;
}
}
cout<<result<<endl;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。