TopCoder SRM 490 (Div 2) Hard Hieroglyphs

問題概要

以下のような簡単な"ヒエログリフ"を考える。

  • ヒエログリフは、それぞれがx軸またはy軸に平行な何本かの線分からなる
  • ヒエログリフの線分の端点の座標は全て整数で、0以上80以下
  • 一つのヒエログリフの線分は交差はするが、重なることはない。


二つのヒエログリフが与えられ、それらをずらして好きなように重ねるとき、見える線分の長さの最小値はいくつか。

解法

最初のヒエログリフが通る線分はbool型の配列などに入れておく。
線分の座標は0以上80以下の整数であるので、第二のヒエログリフの位置は高々160^2通り試せばよい。

ソースコード

int n,m;
bool tate[81][81],yoko[81][81];
vi s1,s2;

bool ck(int y,int x)
{
	return 0<=y&&y<81&&0<=x&&x<81;
}
int solve(int sy,int sx)
{
	int ret=0;
	rep(i,m/4)
	{
		int x1=s2[4*i],y1=s2[4*i+1],x2=s2[4*i+2],y2=s2[4*i+3];
		x1-=sx; x2-=sx; y1-=sy; y2-=sy;
		
		if(x1==x2)
		{
			for(int y=y1;y<y2;y++)if(!ck(y,x1)||!tate[y][x1])ret++;
		}
		else for(int x=x1;x<x2;x++)
		{
			if(!ck(y1,x)||!yoko[y1][x])ret++;
		}
	}
	return ret;
}

class Hieroglyphs {
	public:
	int minimumVisible(vector <string> hier1, vector <string> hier2) 
	{
		s1.clear(); s2.clear();
		string a,b;
		rep(i,hier1.size())a+=hier1[i]+" "; fr(i,a)if(*i==',')*i=' ';
		rep(i,hier2.size())b+=hier2[i]+" "; fr(i,b)if(*i==',')*i=' ';
		
		int t;
		stringstream ss(a); while(ss>>t)s1.pb(t);
		stringstream sss(b); while(sss>>t)s2.pb(t);
		
		n=s1.size(); m=s2.size();
		int len=0;
		rep(i,81)rep(j,81)tate[i][j]=yoko[i][j]=0;
		rep(i,n/4)
		{
			int x1=s1[4*i],y1=s1[4*i+1],x2=s1[4*i+2],y2=s1[4*i+3];
			
			if(x1==x2)for(int y=y1;y<y2;y++)tate[y][x1]=1,len++;
			else for(int x=x1;x<x2;x++)yoko[y1][x]=1,len++;
		}
		
		int ans=inf;
		
		for(int i=-81;i<=81;i++)for(int j=-81;j<=81;j++)
		{
			ans=min(ans,solve(i,j));
		}
		return len+ans;
	}
};