TopCoder SRM 800 : Div1 Easy PoisonedSwamp

またMedium落とした…。
https://community.topcoder.com/stat?c=problem_statement&pm=16768&rd=18497

問題

グリッドが与えられる。
各マスは、

• 通行可能
  • 何も起きない
  • 毒の沼地であり、通るたびにマスに応じたダメージを受ける
  • ダメージを全回復する
• 通行不可能

のいずれかである。
左上マスから右下マスまで、隣接マスをたどり移動したい。
その際、間に全回復を挟まず累積ダメージが10以上になるとそれ以上移動できなくなる。

無事右下マスに移動できるか判定せよ。

解法

各マスに到達可能な最小ダメージを管理し、ダイクストラ法を行うだけ。

int dp[20][20];

class PoisonedSwamp {
	public:
	string cross(vector <string> swamp) {
		int H=swamp.size();
		int W=swamp[0].size();
		MINUS(dp);
		dp[0][0]=9;
		priority_queue<pair<int,int>> Q;
		Q.push({9,0});
		while(Q.size()) {
			int cur=Q.top().first;
			int cy=Q.top().second/100;
			int cx=Q.top().second%100;
			if(cy==H-1&&cx==W-1) return "possible";
			Q.pop();
			if(dp[cy][cx]!=cur) continue;
			int i;
			FOR(i,4) {
				int dd[4]={1,0,-1,0};
				int ty=cy+dd[i];
				int tx=cx+dd[i^1];
				if(ty<0||ty>=H||tx<0||tx>=W) continue;
				if(swamp[ty][tx]=='#') continue;
				int tar=cur;
				if(swamp[ty][tx]=='S') tar=9;
				if(swamp[ty][tx]>='1'&&swamp[ty][tx]<='9') tar=cur-(swamp[ty][tx]-'0');
				if(tar<0) continue;
				if(dp[ty][tx]<tar) {
					dp[ty][tx]=tar;
					Q.push({tar,ty*100+tx});
				}
			}
		}
		return "impossible";
	}
}

まとめ

最小移動回数を求める問題にしてもいいと思ったんだけどな。