SRM551 Div1 Medium(450) ColorfulWolves

TopCoder

ColorfulWolves

色xから色yに変更可能にするコストは、colormap[x][0..y-1]の'Y'の個数。色0から色N-1への最短経路を求めれば良い。

#include <string>
#include <vector>
using namespace std;

class ColorfulWolves{public:
int getmin( vector <string> colormap )
{
    int INF = 99999999;
    int n = (int)colormap.size();

    vector<vector<int> > D(n,vector<int>(n,INF) );
    for ( int i=0; i<n; i++ )
    {
        int c = 0;
        for ( int j=0; j<n; j++ )
            if ( colormap[i][j]=='Y' )
                D[i][j] = c++;
                c++;
    }

    for ( int i=0; i<n; i++ )
    for ( int j=0; j<n; j++ )
    for ( int k=0; k<n; k++ )
        D[j][k] = min( D[j][k], D[j][i]+D[i][k] );

    return D[0][n-1]>=INF ? -1 : D[0][n-1];
}};