Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-31

SRM379 div2 (過去問)

11:16

Hard - TVGameWinnings

ゲームの最高得点, 最低得点を求める. ゲームのルールはややこしいので省略.

問題文は長かったんですが問題自体は900点なので簡単でした. ボードの大きさが高々6なので, すべてのケースで6!通りとなり, 全探索で大丈夫そうです. 探索には next_permutation を使いました. connected なグループ数のカウントにはつながっているセルにラベルを付けていくという flood fill っぽいアルゴリズムを使いました.

class TVGameWinnings {
public:
  int getVal(char s) {
    if ('A' <= s && s <= 'I')
      return (s - 'A' + 1) * -1;
    return s - '0';
  }

  vector <int> getMinMax(vector <string> board) {
    vector <int> ret(2, 0);
    vector <int> indices(board.size(), 0);
    ret[0] = INT_MAX, ret[1] = INT_MIN;
    for (int i=0; i<indices.size(); i++)
      indices[i] = i;

    do {
      vector <int> labels(board.size(), 0);
      int label = 1, cur_pos = 0;

      // count group number
      while (1) {
        labels[cur_pos] = label;
        int next_pos = indices[cur_pos];
        if (labels[next_pos] == 0) {
          cur_pos = next_pos;
        } else {
          int i;
          for (i=0; i<labels.size(); i++)
            if (labels[i] == 0) {
              cur_pos = i;
              break;
            }
          if (i == labels.size()) break;
          label++;
        }
      }

      // calculate score
      int score = 1;
      for (int i=0; i<indices.size(); i++)
        score *= getVal(board[i][indices[i]]);
      
      if (label % 2 == 0)
        score *= -1;

      ret[0] = min(ret[0], score);
      ret[1] = max(ret[1], score);
    } while (next_permutation(indices.begin(), indices.end()));

    return ret;
  }
};