SRM 459 Div2 Hard ParkAmusement

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10723&rd=14145

いくつか島がある。ある人がある島からスタートして、島と島を結ぶ道をK回通ってゴールとなる島へ行きたいとする。
vector landingsが与えられ、landings[i][j]が'1'のとき、島iから島jへの道が通じているとする。landings[i][i]が'E'となる時、これは出口となる島で、'P'の時、これはゲームオーバーとなってしまう島である。ある島から出ている道が複数あった場合、これらが選ばれる確率は均等とする。また、どの島からスタートするかも一様に同じとする。この条件の時startLanding番目の島からスタートしてK回道を通って無事ゴールである島へ到達する確率を求めよ。

やりかた

深さ優先探索+メモ化。'E'の島と'P'の島以外から出発してK回の移動でちょうどゴールとなる島へ至る確率を計算する。それらの確率の和をとっておいて特別にstartLanding番目の島からスタートしたときの確率を割ってやればいい。ちなみにK回未満の移動でゴールの島へ至ってしまっても、その島以外から他の島へ行けないのでゲームオーバーと同じ。

以下ソースコード。

map<pair<int, int>, double> dp;

class ParkAmusement {
public:
  double rec(vector<string> field, int idx, int k){
    if(k == 0){
      if(field[idx][idx] == 'E') return 1.0;
      else return 0.0;
    }
    //check whether reached to goals or crocodiles before moving K times 
    if(field[idx][idx] == 'E' || field[idx][idx] == 'P')
      return 0.0;
    
    if(dp.count(make_pair(idx, k))) return dp[make_pair(idx, k)];

    double prob = 0.0;
    //the number of pipes  from idx-th island
    int pipe = count(field[idx].begin(), field[idx].end(), '1');
    if(pipe){
      for(int j = 0; j < (int)field[0].length(); j++){
	if(field[idx][j] == '1')
	  prob += (rec(field, j, k - 1) * 1.0 / pipe);
      }
    }
    
    return dp[make_pair(idx, k)] = prob;
  }

  double getProbability(vector <string> landings, int startLanding, int K) {
    int N = landings.size();
    dp.clear();
    vector<double> P(N, 0.0);
    double denom = 0;
    for(int i = 0; i < N; i++){
      if(count(landings[i].begin(), landings[i].end(), '1')){
	P[i] = rec(landings, i, K) * 1.0 / N;
      }
      denom += P[i];
    }
    return P[startLanding] / denom;
  }
};

これも一発ACできた。やったーーーー。