AOJ2709 Dark Room

問題

個の部屋があり、そのうち個が暗い部屋である。 各部屋には[tex1]〜に番号付けされたドアがある。 順に進むべきドアの番号を指示する列を与える。一度明るい部屋に到達したら、その続きの指示は無視される。 部屋のどこからスタートしても明るい部屋に到達できるようにしたい。 ドアの列の最小の長さを求めよ。

• 
• 
• 

解法

部屋のどこからでも同じ指示の列で明るい部屋に到達しなければならない。 元々明るい部屋にいる場合は、全ての指示が無視されるので考慮する必要はない。 各々の暗い部屋に1人ずつ配置する。全員同時に移動させて、 暗い部屋にいる人が居なくなるための、最小の指示列の長さを求めれば良い。 また、2人が一度同じ部屋に到達した場合、その後の2人の行動は一致すると考える。

立っているビットを、その部屋にだれかいる場合と見なしてDPし、dp[0]を答えとすれば良い。 一度ある人が訪れた部屋を別の人が訪れる場合があり、for文ではDP出来ないので、BFSで遷移すれば良い。

int main() {
 
  int N, M, K; cin >> N >> M >> K;
 
  map<int, int> mp, mprev;
  int darkcnt = 0;
 
  rep(i, M) {
    int d; cin >> d; d--;
    mp[d] = darkcnt;
    mprev[darkcnt++] = d;
  }
 
  vector<vector<int>> G(N);
 
  rep(i, N) {
    rep(k, K) {
      int to; cin >> to; to--;
      G[i].push_back(to);
    }
  }
 
  int dp[1 << M];
  rep(i, 1 << M) dp[i] = inf;
 
  dp[(1 << M) - 1] = 0;
  queue<int> q;
  q.push((1 << M) - 1);
 
  while(!q.empty()) {
    auto const S = q.front(); q.pop();
    rep(to_dir, K) {
      auto T = S;
      auto TAdd = 0;
      rep(from, M) {
        if(T >> from & 1) {
          T &= ~(1 << from);
          auto to = G[mprev[from]][to_dir];
          if(mp.find(to) != mp.end()) {
            TAdd |= 1 << mp[to];
          }
        }
      }
      T |= TAdd;
      if(dp[T] > dp[S] + 1) {
        dp[T] = dp[S] + 1;
        q.push(T);
      }
    }
  }
 
  cout << dp[0] << endl;
   
  return 0;
}