雑な速解きで前回のロス分を挽回した。
https://community.topcoder.com/stat?c=problem_statement&pm=17599&rd=19227
問題
H*Wの大きさのグリッド上で、スタートとゴールの点が与えられる。
プレイヤーは、スタートの点からゴールの点に移動したい。
プレイヤーは空を飛ぶ装置を持っているが、バッテリーが空である。
以下の条件のもと、移動にかかる最小時間を求めよ。
- 障害物のあるセルは通行不可
- 隣接セルへは、時間1をかけ移動可能
- 穴の開いたセルは、バッテリーの電力量を1消費して1マス通過可能
- バッテリーチャージャーのあるセルでは、時間Tを掛け、バッテリーの電力量を1増やすことができる。バッテリーはいくらでも電力量を増やすことが可能。
解法
状態として現在位置とバッテリーの電力量を持てば、状態数がO((HW)^2)程度なので、そのままダイクストラ法で解ける。
ただ、もっと状態を削減することができる。
一端バッテリーチャージャーのあるマスを通過したら、以降は穴のあるマスを通る際に時間Tを余分にかければ通過可能、と考えれば、電力量を覚える必要がなく、状態数をO(HW)に落とすことができる。
ll dp[55][55][2]; class Jetpack { public: int travel(vector <string> S, int T) { int H=S.size(); int W=S[0].size(); int x,y,i; FOR(y,H) cout<<S[y].size()<<endl; FOR(y,H) FOR(x,W) FOR(i,2) dp[y][x][i]=1LL<<60; int sx,sy,gx,gy; priority_queue<pair<ll,int>> Q; FOR(y,H) FOR(x,W) { if(S[y][x]=='A') { sx=x,sy=y; S[y][x]='.'; dp[y][x][0]=0; Q.push({0,y*50+x}); } if(S[y][x]=='B') { gx=x,gy=y; S[y][x]='.'; } } while(Q.size()) { ll co=-Q.top().first; int cy=Q.top().second/50%50; int cx=Q.top().second%50; int num=Q.top().second/2500; Q.pop(); if(dp[cy][cx][num]!=co) continue; if(cy==gy&&cx==gx) return co; if(S[cy][cx]=='C') { if(dp[cy][cx][1]>co) { dp[cy][cx][1]=co; Q.push({-dp[cy][cx][1],(1)*2500+cy*50+cx}); } } int d[4]={0,1,0,-1}; FOR(i,4) { int ty=cy+d[i]; int tx=cx+d[i^1]; if(ty<0||ty>=H||tx<0||tx>=W) continue; if(S[ty][tx]=='#') continue; if(S[ty][tx]=='_'&&num==0) continue; if(dp[ty][tx][num]>co+1+(S[ty][tx]=='_')*T) { dp[ty][tx][num]=co+1+(S[ty][tx]=='_')*T; Q.push({-dp[ty][tx][num],num*2500+ty*50+tx}); } } } return -1; } }
まとめ
本番雑にO((HW)^2)の状態数のコードを書いてしまったが、通ってよかった。