SRM 396 Div1 Medium FixImage

問題

#か.で描かれた絵がある。#と#が上下左右で隣り合っているとき、それらは接しているといい、接している#の集合を一つの連結成分ということにする。同じ連結成分に属している2つの#には道のりが定義でき、一方の#からもう一方の#までたどり着くまでに経由する最小の#の個数+1で決まる。任意の同連結成分中の任意の2つの#の間の道のりが、それらのマンハッタン距離と等しい時、その絵はスムーズであるという。与えられた絵をスムーズにするために.を#に変更する。変更する数を最小にしつつスムーズにしたときの絵の状態を求めよ。

やりかた

まず初期盤面を連結成分ごとに分ける。そのうえで#に変更する.を調べる。
ある.について#ぶつかるまで左右に調べる。ぶつかった#が同じ連結成分に属しているならばその2つの#の間の道のりはマンハッタン距離と同じにはなりえないので、この2つの#が挟む.は#に変更する必要がある。2つの#が同じ連結成分に属していない、もしくは#が見つからないまま絵の端まで行った場合には調べた場所を#に変更する必要はない。なお上下方向についても同様の調査を行う。
.を#に変更すると連結成分の構成が変わることがあるので、連結成分を列挙 → すべての.を調査 というサイクルを盤面の変更があるかぎりループして行う。

以下ソース。

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

class FixImage {
public:
  int N, M;
  vector<string> ret;
  bool in(int y, int x){ return 0 <= y && y < N && 0 <= x && x < M; }

  void func(int y, int x, int l, vector<vector<int> > &label){
    label[y][x] = l;
    for(int i = 0; i < 4; i++){
      int ny = y + dy[i], nx = x + dx[i];
      if(in(ny, nx) && ret[ny][nx] == '#' && label[ny][nx] == 0)
	func(ny, nx, l, label);
    }
  }
  void cca(vector<vector<int> > &label){ //連結成分ごとにラベルを振る
    int l = 1;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < M; j++)
	if(ret[i][j] == '#' && label[i][j] == 0)
	  func(i, j, l++, label);
  }
  
  vector <string> originalImage(vector <string> alteredImage) {
    N = alteredImage.size(), M = alteredImage[0].size();
    ret = alteredImage;
    bool update = true;
    while(update){ //盤面の更新がある限りループ
      update = false;
      vector<string> tmp = ret;
      vector<vector<int> > la(N, vector<int>(M, 0));
      cca(la);
      for(int i = 0; i < N; i++){
	for(int j = 0; j < M; j++){
	  if(la[i][j] != 0) continue;
	  int wl = 0, el = 0; //左右の#が属している連結成分
	  vector<pair<int, int> > pt;
	  for(int k = j; k >= 0; k--){
	    wl = la[i][k];
	    pt.push_back(make_pair(i, k));
	    if(la[i][k] != 0) break;
	  }
	  for(int k = j + 1; k < M; k++){
	    el = la[i][k];
	    pt.push_back(make_pair(i, k));
	    if(la[i][k] != 0) break;
	  }
	  if(wl == el && wl != 0){ //左右の#が同じ連結成分だった場合
	    update = true;
	    for(int k = 0; k < (int)pt.size(); k++)
	      tmp[pt[k].first][pt[k].second] = '#';
	  }
	  int nl = 0, sl = 0; //上下の#が属している連結成分
	  pt.clear();
	  for(int k = i; k >= 0; k--){
	    nl = la[k][j];
	    pt.push_back(make_pair(k, j));
	    if(la[k][j] != 0) break;
	  }
	  for(int k = i + 1; k < N; k++){
	    sl = la[k][j];
	    pt.push_back(make_pair(k, j));
	    if(la[k][j] != 0) break;
	  }
	  if(nl == sl && nl != 0){ //上下の#が同じ連結成分だった場合
	    update = true;
	    for(int k = 0; k < (int)pt.size(); k++)
	      tmp[pt[k].first][pt[k].second] = '#';
	  }
	}
      }
      ret = tmp;
    }
    return ret;
  }
};