AOJ : 1259 - Colored Cubes

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1259
各面に色が塗られた6面ダイスがn個(1 <= n <= 4)ある.
このとき, n個のダイスを全て等しくするためには, 最小でいくつの面を塗り替えなければならないかを求めよ.
等しいダイスとは, 問題文のFigure3のように, 回転して各面が同じ色になるダイスのことを言う.

アルゴリズム

全通りやるだけ.

計算を高速化させるために, 入力される色の名前（文字列）は, 全て数字に置きなおしておく.
あとは, 以下の通り処理を行う.

• n個のサイコロの置き方を決める (24^4)
  • 各面につき, どのサイコロの色に合わせたら最小の塗り数で済むかを計算する (6 * 4)
    • 二重ループで計算
  • これを合計する
  • 答えの更新

プログラム

class Dice{
public:
  int t,s,e,n,w,b; //上,南,東,北,西,下
  Dice(){}
  Dice(int _t,int _s,int _e,int _n,int _w,int _b){
    t = _t; s = _s; e = _e; n = _n; w = _w; b = _b;
  }
  Dice moveEast(){
    return Dice(w,s,t,n,b,e);
  }
  Dice moveNorth(){
    return Dice(s,b,e,t,w,n);
  }
  Dice moveRight(){
    return Dice(t,e,n,w,s,b);
  }
  void toTable(int *res){
    res[0] = t;
    res[1] = s;
    res[2] = e;
    res[3] = n;
    res[4] = w;
    res[5] = b;
  }
};

//全ての置き方を生成する
vector<Dice> makeDice(Dice d){
  vector<Dice> res;

  rep(i,6){
    rep(j,4){
      res.push_back(d);
      d = d.moveRight();
    }
    if(i < 4) d = d.moveEast();
    else if(i == 4) d = d.moveNorth();
    else if(i == 5) d = d.moveNorth().moveNorth();
  }

  return res;
}

map<string,int> name;
int n;
vector<Dice> d[4];

//色の名前を整数に変換する
int trans(string s){
  if(name.find(s) == name.end()){
    int tmp = name.size();
    name[s] = tmp;
  }
  return name[s];
}

//n個のサイコロの置き方が与えられたとき, 最小の塗り替え数を返す
int calc(int *t){
  int res = 0;
  int v[n][6];
  rep(i,n) d[i][t[i]].toTable(v[i]);

  rep(i,6){
    int maxCnt = 0;
    int cnt[24];
    memset(cnt,0,sizeof(cnt));
    rep(j,n){
      cnt[v[j][i]]++;
      if(maxCnt < cnt[v[j][i]]) maxCnt = cnt[v[j][i]];
    }
    res += n - maxCnt;
  }

  return res;
}

//答えを再帰で求める
int solve(int idx,int *t){
  if(idx == n){
    return calc(t);
  }

  int res = INT_MAX;
  rep(i,24){
    t[idx] = i;
    res = min(res,solve(idx+1,t));
  }

  return res;
}

int main(void){
  while(cin>>n,n){
    name.clear();

    rep(i,n){
      int num[6];

      rep(j,6){
        string s;
        cin>>s;
        num[j] = trans(s);
      }

      d[i] = makeDice(Dice(num[2],num[0],num[1],num[5],num[4],num[3]));
    }

    int t[n];
    cout<<solve(0,t)<<endl;
  }
}