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: 2017年11月19日12時14分23秒
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)

ログイン: