TopCoder SRM 387 Div1 Easy MarblesRegroupingEasy

TopCoder

問題

n個の箱にそれぞれi種類目のマーブルがboxes[i][j]個入っている。
何度か操作を繰り返して、次の状態を満たすようにしたい。

  • 一つのjoker boxを決める。
  • joker box以外の箱は、空であるか一種類のマーブルしか入っていない。
  • 一種類のマーブルは、joker box以外の箱のうち、二つ以上に入っていない。


操作：ある箱のマーブルを全て取り、別の箱に全て入れる。

制約条件

boxes[i][j]≦9
n≦50

方針

joker boxをn通り試す。
joker boxを決めた後は、
複数種類のマーブルが入っている箱があったら、その箱の中身は全てjoker boxに入れる。
その後で、残ったマーブルが別の箱に散らばっていたら、一つを残して全てjoker boxに入れる。
ようにすれば最短回数で条件を満たすことができる。

ソースコード

class MarblesRegroupingEasy {
  public:
  int minMoves(vector <string> boxes) {
    int n=boxes.size(), m=boxes[0].size();
    int ans=inf;
    rep(jk,n){
      vector<vi> num(n,vi(m));
      rep(i,n)rep(j,m)num[i][j]=boxes[i][j]-'0';
      int cnt=0;
      rep(i,n)if(i!=jk){
        int c=0;
        rep(j,m)if(num[i][j])c++;
        if(c<2)continue;
        cnt++;
        rep(j,m)num[i][j]=0;
      }
      rep(i,m){
        int c=0;
        rep(j,n)if(j!=jk&&num[j][i])c++;
        cnt+=max(0,c-1);
      }
      ans=min(ans,cnt);
    }
    return ans;
  }
};