SRM551 Div1 Medium

450

変更の回数をコストにしてダイクストラする。

class ColorfulWolves {
public:
  int getmin(vector <string> cm)
  {
    const int N = 50 + 1;

    bool g[N][N];
    fill(&g[0][0], &g[N - 1][N - 1] + 1, false);

    const int V = cm.size();

    for (int i = 0; i < V; ++i) {
      for (int j = 0; j < V; ++j) {
        g[i][j] = (cm[i][j] == 'Y');
      }
    }

    map<int, int> cost;
    set<int> vis;
    priority_queue< pair<int, int> > q;

    for (q.push(make_pair(0, 0)); q.size(); ) {
      int curr = q.top().second;
      int change = -1 * q.top().first;
      q.pop();
      if (vis.count(curr)) continue;
      vis.insert(curr);
      cost[curr] = change;
      int cnt = 0;
      for (int next = 0; next < N; ++next) {
        if (g[curr][next] && !vis.count(next)) {
          q.push(make_pair(-(change + cnt), next));
        }
        if (g[curr][next]) ++cnt;
      }
    }
    return vis.count(V - 1) ? cost[V - 1] : -1;
  }
};