SRM506 Div2 Hard(1000) 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; }};