問題
http://community.topcoder.com/stat?c=problem_statement&pm=8527&rd=11121
解き方
全てのjoker boxの選び方について全探索する。
joker box以外の箱について２色以上入っている箱は必ず動かさなければいけない。
そのため１色しか入っていない箱のみ調べ、
使っていない色であればその色を割り当てていけばよい。
コード
class MarblesRegroupingEasy {
public:
int minMoves(vector<string> boxes) {
int n=boxes.size(),m=boxes[0].size();
int used[m];
int ret=1e+9;
FORE(i,0,n){
int cost=0;
memset(used,0,sizeof(used));
FORE(j,0,n)if(i!=j){
int cnt=0,color=-1;
FORE(k,0,m)if(boxes[j][k]!='0')cnt++,color=k;
if(cnt==0)continue;
if(cnt==1 && used[color]==0)used[color]=1;
else cost++;
}
ret=min(ret,cost);
}
return ret;
}
};
public:
int minMoves(vector<string> boxes) {
int n=boxes.size(),m=boxes[0].size();
int used[m];
int ret=1e+9;
FORE(i,0,n){
int cost=0;
memset(used,0,sizeof(used));
FORE(j,0,n)if(i!=j){
int cnt=0,color=-1;
FORE(k,0,m)if(boxes[j][k]!='0')cnt++,color=k;
if(cnt==0)continue;
if(cnt==1 && used[color]==0)used[color]=1;
else cost++;
}
ret=min(ret,cost);
}
return ret;
}
};