color.cpp

对于给定的矩形区域和指定的颜色,计算rob拿起喷枪的最少次数.

#include<fstream.h>   
#include<memory.h>

#define MAXn 50
#define MAXx 25
#define MAXy 25

int po2[MAXn];
int c[MAXn];
int g[MAXn][MAXn];
int m[MAXn][MAXn*MAXn];
int n;
void comp();
   
void bt(int r,int p)
{
	if(m[r][p]>=0) return;
	for(int i=0;i<n;++i)
		if(i!=r&&(p&po2[i])&&g[i][r])
			{
			m[r][p]=MAXx;
			return;
			}
		int np=p-po2[r];
		if(np==0) 
			m[r][p]=1;
		else
			for(i=0;i<n;++i)
				if(np&po2[i])
					{
					bt(i,np);
					int v=m[i][np]+(c[r]==c[i]?0:1);
					if(m[r][p]<0||m[r][p]>v) 
						m[r][p]=v;
					}
}

void comp()
{
	memset(m,-1,sizeof(m));
	int opt=-1;
	for(int i=0;i<n;++i)
		{
		bt(i,po2[n]-1);
		if(opt<0||opt>m[i][po2[n]-1])
			opt=m[i][po2[n]-1];
		}
	ofstream output("output.txt");
	output<<opt;
}

void init()
{
	int b[MAXx][MAXy];
	ifstream input("input.txt");
	input>>n;
	memset(b,-1,sizeof(b));
	for(int i=0;i<n;++i)
		{
		int x1,y1,x2,y2;
		input>>x1>>y1>>x2>>y2>>c[i];
		for(int j=x1;j<x2;++j)
			for(int k=y1;k<y2;++k)
				b[j][k]=i;
		}
	memset(g,false,sizeof(g));
	for(i=0;i<MAXx;++i)
		for(int j=0;j<MAXy;++j)
			if(b[i][j]>=0&&b[i+1][j]>=0&&b[i][j]!=b[i+1][j])
				g[b[i][j]][b[i+1][j]]=1;
}

void main()
{
	po2[0]=1;
	for(int i=1;i<MAXn;++i) 
		po2[i]=po2[i-1]<<1;
	init();
	comp();
}