SRM468 Div2 Hard(1000) Gifts

Gifts

贈り物・王・王妃の間の最短距離を予め求めておく。位置と持っている贈り物を状態として、動的計画法。ある地点xで贈り物を拾わない場合は、xを通らなかったとみなせる。

#include <string>
#include <vector>

using namespace std;

class Gifts
{
    int countbit( int n );
public:
    int maxGifts( vector <string> city, int T );
};

int Gifts::maxGifts( vector <string> city, int T )
{
    int h = (int)city.size();
    int w = (int)city[0].size();

    //  贈り物の個数を数え、贈り物・王・王妃に番号を振る
    //  gn：贈り物の個数
    //  王：gn、王妃：gn+1
    int gn = 0;
    vector<vector<int> > index( h, vector<int>( w, -1 ) );

    for ( int y=0; y<h; y++ )
    for ( int x=0; x<w; x++ )
        if ( city[y][x] == 'G' )
            index[y][x] = gn++;

    for ( int y=0; y<h; y++ )
    for ( int x=0; x<w; x++ )
    {
        if ( city[y][x] == 'K' )  index[y][x] = gn;
        if ( city[y][x] == 'Q' )  index[y][x] = gn + 1;
    }

    //  贈り物・王・王妃の間の最小距離を求める
    vector<vector<int> > dist( gn+2, vector<int>( gn+2 ) );

    for ( int fy=0; fy<h; fy++ )
    for ( int fx=0; fx<w; fx++ )
    if ( index[fy][fx] >= 0 )
    {
        vector<vector<int> > map( h, vector<int>( w, T+1 ) );
        map[fy][fx] = 0;

        bool up = true;
        for ( int d=0; up; d++ )
        {
            up = false;

            for ( int y=0; y<h; y++ )
            for ( int x=0; x<w; x++ )
            if ( map[y][x] == d )
            {
                for ( int dir=0; dir<4; dir++ )
                {
                    int tx = x + dir/2     * ( 1 - dir%2*2 );
                    int ty = y + (1-dir/2) * ( 1 - dir%2*2 );

                    if ( 0 <= tx  &&  tx < w  &&
                         0 <= ty  &&  ty < h  &&
                         city[ty][tx] != '#'  &&
                         map[ty][tx] == T + 1 )
                    {
                        map[ty][tx] = d + 1;
                        up = true;
                    }
                }
            }
        }

        for ( int y=0; y<h; y++ )
        for ( int x=0; x<w; x++ )
        if ( index[y][x] >= 0 )
            dist[ index[fy][fx] ][ index[y][x] ] = map[y][x];
    }

    //  位置pに贈り物gを持って到達する最小時刻を求める
    //  i番目のビットでi番目の贈り物を表す
    vector<vector<int> > time( gn+2, vector<int>(1<<gn,T+1) );  //  [p][g]
    for ( int p=0; p<gn+2; p++ )
        time[p][0] = dist[gn][p];

    for ( int n=0; n<=gn; n++ )
    {
        for ( int p=0; p<gn+2; p++ )
        for ( int g=0; g<(1<<gn); g++ )
        if ( countbit(g) == n  &&
             time[p][g] < T + 1 )
        {
            for ( int q=0; q<gn+2; q++ )
            if ( dist[p][q] <= T )
            {
                int gt = p<gn ? g|1<<p : g;
                time[q][gt] = min( time[q][gt],
                                   time[p][g] + (countbit(gt)+1)*dist[p][q] );
            }
        }
    }

    //  王妃の位置について、最小到達時刻がT以内で、
    //  贈り物の個数が最大であるものが答え
    int ans = 0;

    for ( int g=0; g<(1<<gn); g++ )
        if ( time[gn+1][g] <= T )
            ans = max( ans, countbit(g) );

    return ans;
}

int Gifts::countbit( int n )
{
    n = ( n & 0x55555555 ) + ( n >> 1 & 0x55555555 );
    n = ( n & 0x33333333 ) + ( n >> 2 & 0x33333333 );
    n = ( n & 0x0f0f0f0f ) + ( n >> 4 & 0x0f0f0f0f );
    n = ( n & 0x00ff00ff ) + ( n >> 8 & 0x00ff00ff );
    n = ( n & 0x0000ffff ) + ( n >>16 & 0x0000ffff );
    return n;
}