割とオーソドックスな問題。
http://yukicoder.me/problems/15
問題
N*Nの2次元グリッドがあり、各セルには進入コストL[y][x]が設定されている。
始点・終点が与えられるので、始点から終点に総コストがV未満となる範囲で隣接セルを辿り終点に移動したい。
最小移動回数は何回か。
解法
オーソドックスな探索問題。
以下のどちらを状態として探索してもよい。
- dp[総コスト][座標]=最小移動回数
- dp[移動回数][座標]=最小総コスト
Vの最大値が10000、移動回数もO(N^2)なのでかかる時間のオーダーは同じぐらい。
int N,V,SX,SY,GX,GY; int L[101][101]; int HP[2][101][101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>V>>SX>>SY>>GX>>GY; FOR(y,N) FOR(x,N) cin>>L[y][x]; SX--,SY--,GX--,GY--; HP[0][SY][SX]=V; FOR(i,10001) { int cur=i%2,tar=cur^1; ZERO(HP[tar]); j=0; FOR(y,N) FOR(x,N) if(HP[cur][y][x]>0) { j++; FOR(k,4) { int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1}; int tx=x+dx[k],ty=y+dy[k]; if(tx<0 || tx>=N || ty<0 || ty>=N) continue; if(HP[cur][y][x]>L[ty][tx]) HP[tar][ty][tx]=max(HP[tar][ty][tx],HP[cur][y][x]-L[ty][tx]); } } if(HP[tar][GY][GX]>0) return _P("%d\n",i+1); } return _P("-1\n"); }
まとめ
このころは4方向の隣接セル探索にdx,dyを使ってたね。