SRM506 Div2 Hard(1000) SlimeXResidentSlime

SlimeXResidentSlime

スライムが10匹以上ならクリアは不可能。スライムが9匹以下ならば事前に距離を求めておくことで、順番を全通り試すことができる。問題文中のプレイヤーが死んだスライムの上に乗るとスライムが生き返るという記述は、その直後に改めてスライムを殺すためで、気にする必要は無い。

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

//  (sx,sy)-(gx,gy)の最短経路を求める
//  到達不可能ならば-1
int maze( vector<string> map, int sx, int sy, int gx, int gy )
{
    int h=(int)map.size(),w=(int)map[0].size();
    vector<vector<int> >D(h,vector<int>(w,-1));
    D[sy][sx]=0;
    int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
    for(int d=0;;d++){
        if(D[gy][gx]==d)return d;
        bool up=false;
        for(int y=0;y<h;y++)for(int x=0;x<w;x++)if(D[y][x]==d)
            for(int i=0;i<4;i++){
                int tx=x+dx[i],ty=y+dy[i];
                if(0<=tx&&tx<w&&0<=ty&&ty<h&&map[ty][tx]!='#'&&D[ty][tx]==-1)
                    D[ty][tx]=d+1,up=true;}
        if(!up)break;}
    return -1;
}

class SlimeXResidentSlime{public:
int exterminate( vector <string> field )
{
    int R = (int)field.size();
    int C = (int)field[0].size();

    int INF = 99999999;

    vector<int> sx, sy, power;
    for ( int y=0; y<R; y++ )
    for ( int x=0; x<C; x++ )
        if ( field[y][x]=='$' )
            sx.push_back(x),
            sy.push_back(y),
            power.push_back(INF);
    for ( int y=0; y<R; y++ )
    for ( int x=0; x<C; x++ )
        if ( '1'<=field[y][x] && field[y][x]<='9' )
            sx.push_back(x),
            sy.push_back(y),
            power.push_back(field[y][x]-'0');
    int n = (int)sx.size();
    if ( n>=11 )
        return -1;

    vector<vector<int> > D(n,vector<int>(n));
    for ( int i=0; i<n; i++ )
    for ( int j=i; j<n; j++ )
    {
        int d = maze( field, sx[i], sy[i], sx[j], sy[j] );
        if ( d < 0 )
            return -1;
        D[i][j] = D[j][i] = d;
    }

    vector<int> slim;
    for ( int i=0; i<n; i++ )
        slim.push_back(i);
    int ans = INF;
    do
    {
        int d = 0;
        bool f = true;
        for ( int i=n-2; i>=0; i-- )
        {
            d += D[slim[i]][slim[i+1]];
            if ( power[slim[i]] <= d )
                f = false;          
        }
        if ( f )
            ans = min(ans,d);
    }
    while( next_permutation(slim.begin()+1,slim.end()) );

    return ans<INF ? ans : -1;
}};