問題概要
以下のような簡単な"ヒエログリフ"を考える。
- ヒエログリフは、それぞれが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;
}
};