1783: 喷漆机器人问题

题目描述

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

参考代码

#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;
}

解析

暂无