TopCoderOpen Algorithm 2014 Round 1B MEDIUM - WolvesAndSheep

Source

TopCoderOpen Algorithm 2014 Round 1B MEDIUM (600pt)
Problem Statement

問題概要

$R$ 行 $C$ 列の盤面が与えられる．
各マスは，空か，動物Aがいるか，動物Bがいる，のどれかである．
行と行の間か，列と列の間にフェンスを建てることができる．交わっても良い．
フェンスで仕切られた各区画には，高々1種類の動物しかいないようにしたい．
最小で何個のフェンスを建てれば良いかを求める問題．

解法

横向きのフェンスはどこに作るかを $2^{R-1}$ 通り全部試し，縦向きのフェンスはGreedyに建てる．
横向きのフェンスが無いと決めた場所については，その上下の行を合体させる．
その際，2種類の動物が混在するセルができるようならば，そのような横向きのフェンスの建て方は不可能．
縦向きのフェンスは，左から建てるかどうかを決めて行って，ここで建てないなら2種類の動物が混在する，という場合だけ建てるようにする．

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class WolvesAndSheep {
public:
int getmin(vector <string> in) {
  int i, j, k;
  int x = in.size(), y = in[0].size();
  int mask;
  int mp[20][20];
  int res = 100000, tmp;

  rep(mask,1<<(x-1)){
    tmp = 0;
    rep(i,x) rep(j,y) mp[i][j] = 0;
    rep(i,x){
      rep(j,y) if(in[i][j]=='W') mp[tmp][j] |= 1;
      rep(j,y) if(in[i][j]=='S') mp[tmp][j] |= 2;
      if(mask & 1<<i) tmp++;
    }
    k = 0;
    rep(i,x) rep(j,y) if(mp[i][j]==3) k++;
    if(k) continue;

    REP(j,1,y){
      rep(i,x) if((mp[i][j-1]|mp[i][j])==3) break;
      if(i==x){
        rep(i,x) if(mp[i][j]==0) mp[i][j] = mp[i][j-1];
      } else {
        tmp++;
      }
    }
    res = min(res, tmp);
  }

  return res;
}

}

Current time: 2024年04月20日00時31分06秒
Last modified: 2014年04月20日06時19分38秒 (by laycrs)
Tags: Competitive_Programming TopCoder TopCoderOpen TCO_Algorithm TCO_Algorithm_2014 TCO_Algorithm_2014_1B
トップページに戻る

Logged in as: unknown user (not login)

ログイン：