変更の回数をコストにしてダイクストラする。
- 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;
- }
- };