Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-11-14

SRM425 Div1 Medium: PiecesMover

| 18:12 | SRM425 Div1 Medium: PiecesMover - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM425 Div1 Medium: PiecesMover - naoya_t@topcoder SRM425 Div1 Medium: PiecesMover - naoya_t@topcoder のブックマークコメント

夕方の珈琲館で解いてみた。

  1. 5つの駒を寄せた時に出来るパターンは571通り。駒の数が4つ以下ならもっと少ない。
    • 全パターン生成は 25C5 通りの組合せの中で5駒が繋がっているものを抽出。
    • 5駒が繋がっているかどうかを調べるのがこの問題で一番面倒な箇所かも
  2. その全パターンに対し、5個の駒を寄せて移動数合計を調べ、合計最小移動数を求める
    • パーキングロット問題(最適ペアマッチング?)みたいだけど、最大5対5なので全ての組合せを調べても5!=120通りなので全部やる
    • 駒の初期位置が偏っている場合には盤のサイズを5x5より小さくできるが、特にやる意味はなさそう。

結論:冷静に考えればこれは余裕の問題。

#include <string>
#include <vector>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class PiecesMover {

  // 駒の位置が立ったintを pair<int,int> のベクタに変換して返す
  vector<pair<int,int> > pattern(int x)
  {
    vector<pair<int,int> > ms(__builtin_popcount(x));
    int msi = 0;
    for (int i=0,m=1<<24; i<25; i++,m>>=1)
      if (x & m) ms[msi++] = make_pair(i/5,i%5);
    return ms;
  }

  // 駒がすべて繋がっているか調べる
  bool is_possible_pattern(const vector<pair<int,int> > &ms)
  {
    int n = sz(ms);
    vector<bool> ok(n,false), // 駒が#0から(直接もしくは間接的に)導通しているか
                    ck(n,false); // 調査済みか
    ok[0] = true;
    int okc = 1;

    bool om[7][7]; // 導通マップ
    for (int i=1;i<=5;i++) for (int j=1;j<=5;j++) om[i][j] = 0;

    while (1) {
      int cx = -1; // 未調査の駒を1つ選ぶ。(最初は 0 が選ばれる)
      for (int i=0;i<n;i++) if (ok[i] && !ck[i]) { cx=i; break; }
      if (cx == -1) break; // 未調査の駒がなくなればループ終了

      // 調査対象の駒の上下左右のセルを、導通マップ上でtrueにする。
      // 7x7にしてるのはここの便宜のため
      int x = 1+ms[cx].first, y = 1+ms[cx].second;
      om[x-1][y] = om[x+1][y] = om[x][y-1] = om[x][y+1] = true;

      // 未導通の駒iを探し、新たに導通していればok[i]をtrueにする
      for (int i=1;i<n;i++) {
        if (!ok[i]) {
          int x = 1+ms[i].first, y = 1+ms[i].second;
          if (om[x][y]) { ok[i]=true; okc++; }
        }
      }

      ck[cx] = true; // 調査済
    }

    // 全駒が導通していればtrue、さもなければfalseを返す
    return (okc == n);
  }

  // 2点間の距離
  int distance(pair<int,int> p1, pair<int,int> p2)
  {
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
  }
public:
  int getMinimumMoves(vector<string> board) {
    vector<pair<int,int> > pieces; // 駒の位置
    for (int r=0; r<5; r++)
      for (int c=0; c<5; c++)
        if (board[r][c]=='*') pieces.pb(make_pair(r,c));

    // すでに全駒導通していれば 0 を返す
    if (is_possible_pattern(pieces)) return 0;

    int N = sz(pieces), Nx = 1; // N=駒の数, Nx=N!
    for (int i=2; i<=N; i++) Nx*=i; // N!

    // 全ての導通パターンについて調べる
    int minimum_distance = INT_MAX;
    for (int i=(1<<25)-1; i>=0; i--) {
      if (__builtin_popcount(i) != N) continue;
      // ビットがN個立っているパターンのみ残る

      vector<pair<int,int> > pat = pattern(i);
      if (!is_possible_pattern(pat)) continue;
      // 全駒が導通しているパターンのみ残る

      vector<int> v(N); for(int i=0; i<N; i++) v[i] = i; // int v[5] = { 0,1,2,3,4 }
      for (int i=0; i<Nx; i++) { // N対Nの全組合せについて、合計移動距離を求め最小値と比較
        int total_distance = 0;
        for (int j=0;j<N;j++) total_distance += distance(pieces[j], pat[v[j]]);
        if (total_distance < minimum_distance) minimum_distance = total_distance;
        next_permutation(all(v));
      }
    }
    return minimum_distance;
  }
};

最悪のケースでも565msec前後で解けているようだ。

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20081114