SRM 551 div1 med: ColorfulWolves

問題

TopCoder Statistics - Problem Statement

あるオオカミは, 毎夜毛の色を変える。毛は colormap[i][j] = Y のとき i -> j に色を変えることができる。毛を変えるアルゴリズムは, colormap[i][j] = Y を満たす 最小の j に毛の色を変える, というものである。このオオカミは, 毛の色を(一日で良いので) N-1 に変えたい。そのために, colormap 情報の Y の部分を N に変更できる。この変更の最小回数を求めよ。

解法

同じところに戻ってくるのが無駄である(というかそうなったら N-1 にたどり着くことはできない)ことがわかるとどの頂点も高々 1 回しか通らないということができます。

なので, dp[i] = (色 i に到達するまでに必要な最小変更回数)というのを最短経路風に更新していけば解けます。

const int INF = 1e9;
int dp[55];

class ColorfulWolves {
public:
    int getmin(vector <string> colormap) {
        int n = colormap.size();
        for (int i = 0; i < n; i++) {
            dp[i] = INF;
        }
        dp[0] = 0;
        for (int _ = 0; _ < n*n; _++) {
            for (int i = 0; i < n; i++) if (dp[i] < INF) {
                int cnt = 0;
                for (int j = 0; j < n; j++) {
                    if (colormap[i][j] == 'Y') {
                        dp[j] = min(dp[j], dp[i]+cnt);
                        cnt++;
                    }
                }
            }
        }
        if (dp[n-1] == INF) return -1;
        return dp[n-1];
    }
    };