喷漆机器人问题

喷漆机器人问题

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注