naoya_t@topcoder

SRM425 Div1 Medium: PiecesMover

過去問, 練習 | 18:12 |

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

1. ５つの駒を寄せた時に出来るパターンは571通り。駒の数が４つ以下ならもっと少ない。
   • 全パターン生成は 25C5 通りの組合せの中で５駒が繋がっているものを抽出。
   • ５駒が繋がっているかどうかを調べるのがこの問題で一番面倒な箇所かも
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; // 未調査の駒を１つ選ぶ。（最初は 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前後で解けているようだ。