SRM 498 Div2 Hard NinePuzzle

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11225&rd=14427

ピラミッド型の8パズルの初期局面とゴールとなる局面が与えられる。任意のピースを任意の回数動かして初期局面からゴールとなる最終局面まで遷移したい。遷移できないときは初期局面のピースの色を塗り替えて良い。最終局面を得るために必要な塗り替えの最小回数を求めよ。

やりかた

１5パズルと異なり、このパズルはピースの色と種類が一致しているなら、どんな状態間でも遷移できる。つまりどんな局面にもできる。簡単にして、２パズルで考えてみるといい。
となると、もともと各色のパネル数の違いのみが問題になる。これを調べればいい。

以下ソース。

class NinePuzzle {
public:
  int getMinimumCost(string init, string goal) {
    int result = 0;
    map<char, int> in, go;
    for(int i = 0; i < (int)init.length(); i++)
      in[init[i]]++, go[goal[i]]++;

    result += abs(in['R'] - go['R']) + abs(in['G'] - go['G'])
      + abs(in['B'] - go['B']) + abs(in['Y'] - go['Y']);
    result /= 2;
    
    return result;
  }
};

これはすぐわかってできた。やった！

でも本番AC数３１１人て多すぎィ！