SRM 490 Div2 Hard Hieroglyphs

問題

x軸かy軸に平行な線分をいくつかくみあわせたヒエログリフが2つ与えられる。ヒエログリフは線分同士が交差したり、接触することはあるが、重なることはないとする。また線分は限りなく細いものとし、交差点の大きさは無限小とする。
2つのヒエログリフを並進移動して重ね、重ねた後の線分の長さの合計を最小化せよ。

やりかた

ヒエログリフ1を固定して、ヒエログリフ2のみを動かすようにする。
ひとつのヒエログリフの大きさは制約から80x80の大きさ以内に収まるので全探査が余裕。ヒエログリフ1に対して下の図のようにヒエログリフ2を全体をなめるように移動してみて、そのたびごとに重ねた線分の合計値を計算してみればいい。

線分の長さをチェックする方法は、線分の位置情報をbool配列row, colに入れて、trueの個数を数えればいい。ただし、ヒエログリフの位置に予めオフセットを加えておかないと探査の段階で配列の負のインデックスにアクセスしかねないので、そこを気をつける。

以下ソース。

struct Hiero{
  int p[4];
};

bool row[300][300], col[300][300];

class Hieroglyphs {
public:
  /* string to int */
  int stoi(string s){
    stringstream ss;
    ss << s;
    int a;
    ss >> a;
    return a;
  }

  //入力形式をパース
  void parse(vector<Hiero> &a, vector<string> hier){
    for(int i = 0; i < (int)hier.size(); i++){
      for(int j = 0; j < (int)hier[i].length(); j++)
	if(hier[i][j] == ',') hier[i][j] = ' ';

      int idx = 0;
      stringstream ss;
      string s;
      Hiero tmp;
      ss << hier[i];
      while(ss >> s){
	tmp.p[idx++ % 4] = stoi(s);
	if(idx == 4){
	  idx = 0;
	  a.push_back(tmp);
	}
      }
    }
    return;
  }
  void check(vector<Hiero> &seg, int &cnt, bool flag){
    for(int i = 0; i < (int)seg.size(); i++){
      if(seg[i].p[0] == seg[i].p[2]){ // |
	for(int j = seg[i].p[1]; j < seg[i].p[3]; j++){
	  if(!col[seg[i].p[0]][j]){ cnt++;
	    if(flag) col[seg[i].p[0]][j] = true;
	  }
	}
      }else{ // -
	for(int j = seg[i].p[0]; j < seg[i].p[2]; j++){
	  if(!row[seg[i].p[1]][j]){
	    cnt++;
	    if(flag) row[seg[i].p[1]][j] = true;
	  }
	}
      }
    }
  }
  int minimumVisible(vector <string> hier1, vector <string> hier2) {
    int result = INF;
    vector<Hiero> seg1, seg2;
    parse(seg1, hier1);
    parse(seg2, hier2);

    //ヒエログリフにオフセット100を加える
    for(int i = 0; i < (int)seg1.size(); i++)
      for(int j = 0; j < 4; j++) seg1[i].p[j] += 100;
    for(int i = 0; i < (int)seg2.size(); i++)
      for(int j = 0; j < 4; j++) seg2[i].p[j] += 100;


    memset(row, false, sizeof(row)); memset(col, false, sizeof(col));

    //ヒエログリフ1の線分長
    int cnt1 = 0;
    check(seg1, cnt1, true);

    //ヒエログリフ2をヒエログリフ1全体にわたって移動させてみる
    for(int y = -100; y <= 100; y++){
      for(int x = -100; x <= 100; x++){
        //ヒエログリフ2を+x, +y移動させる
	vector<Hiero> seg3 = seg2;
	for(int i = 0; i < (int)seg2.size(); i++)
	  for(int j = 0; j < 4; j++) seg3[i].p[j] += (j % 2 == 0) ? x : y;
	
        //ヒエログリフ2の線分長。ただし1と重なる部分は数えない。
	int cnt2 = 0;
	check(seg3, cnt2, false);

	result = min(result, cnt1 + cnt2);
      }
    }

    return result;
  }
};

問題自体がそこまで難しいことを要求しないぶん入力形式が面倒。
初めて見た時はまったくわからなかったが、逆に今見るとなぜできなかったのか不思議に思える。できるようになったと思って喜ぼう。