TopCoder SRM 396 Div1 Medium FixImage

問題

各マスが#または.からなる画像が与えられる。
画像は以下の性質を満たしている。

#のマスのそれぞれの連結成分について（ただし、二つのマスが連結しているとは辺を共有しているマスをたどって一方のマスからもう一方のマスへ移動できることをいう）、
任意の2つのマスをx,yとすると、
xからyへの「長さがxとyのマンハッタン距離に等しい」パスが存在する。

ここで、(a,b)と(c,d)のマンハッタン距離は|a-c|+|b-d|である。

画像の#のマスがいくつか.に変わっている。
元の画像としてありえるもののうち、#の数が最小であるものを求めよ。
答えが一意に定まることは保証されている。

制約条件

画像の高さ≦50
画像の幅≦50

方針

局所改善を繰り返す。
#...#
#####
のように、同じ連結成分に属している#のうち、
同じ行（または列）に離れた#が二つあったら、その間は埋められなければならない。

これを更新がなくなるまで繰り返せばよい。
実装ゲー。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
vs I;
bool v[50][50],update;
int R[50],r[50],C[50],c[50];
int h,w;

void dfs(int y,int x){
  if(update)return;
  
  if(R[y]!=-1&&!(r[y]<=x&&x<=R[y])){
    for(int i=min(x,r[y]);i<=max(x,R[y]);i++)I[y][i]='#';
    update=1; return;
  }
  if(C[x]!=-1&&!(c[x]<=y&&y<=C[x])){
    for(int i=min(y,c[x]);i<=max(y,C[x]);i++)I[i][x]='#';
    update=1; return;
  }
  if(R[y]<0)R[y]=r[y]=x;
  if(C[x]<0)C[x]=c[x]=y;
    
  for(int i=y;i>=0&&I[i][x]=='#';i--)C[x]=max(C[x],i), c[x]=min(c[x],i);
  for(int i=y;i<h&&I[i][x]=='#';i++)C[x]=max(C[x],i), c[x]=min(c[x],i);
  for(int i=x;i>=0&&I[y][i]=='#';i--)R[y]=max(R[y],i), r[y]=min(r[y],i);
  for(int i=x;i<w&&I[y][i]=='#';i++)R[y]=max(R[y],i), r[y]=min(r[y],i);
  v[y][x]=1;
  
  rep(d,4){
    int ny=y+dy[d],nx=x+dx[d];
    if(ny<0||nx<0||ny>=h||nx>=w||I[ny][nx]=='.'||v[ny][nx])continue;
    dfs(ny,nx);
    if(update)return;
  }
}
class FixImage {
  public:
  vector <string> originalImage(vector <string> in) {
    I=in;
    h=I.size(); w=I[0].size();
    
    for(;;){
    
      rep(i,h)rep(j,w)if(!v[i][j]&&I[i][j]=='#'){
        update=0;
        memset(v,0,sizeof(v));
        rep(k,h)R[k]=r[k]=-1;
        rep(k,w)C[k]=c[k]=-1;
        dfs(i,j);
        if(update)goto NEXT;
      }
      if(!update)break; NEXT:;
    }
    return I;
  }
};