Codeforces #192 Div1. B. Biridian Forest

さてB。
http://codeforces.com/contest/329/problem/B

問題

2次元グリッドが与えられる。
ここでスタートマスからゴールマスまで障害物マスを通らずに移動したい。

プレイヤーは時間１で１マス移動できる。
この時、いくつかのマスには敵キャラがいて同様に時間１で1マスずつ移動する。
敵が最善手を取って移動する場合、プレイヤーがゴールに到達するまでに遭遇する敵キャラ数を最小化し、その数を答えよ。

解法

敵がどう動くか…と考えると難しい。

ここで、ゴールにまっすぐ向かうと敵に遭遇するから遠回りするという手段は役に立たない。
敵がゴールに先回りしてしまえば結局ゴールで遭遇する。

この事実から、結局プレイヤーよりゴールに近い敵は結局ゴールで遭遇することになる。
よってDFSでゴールからの距離を求め、プレイヤーと同じかより近い敵キャラ数をカウントすればよい。

int W,H;
int sx,sy,ex,ey;
string S[1001];
int dist[1001][1001];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(y,H) FOR(x,W) {
		if(S[y][x]=='S') {S[y][x]='0'; sx=x;sy=y;}
		if(S[y][x]=='E') {S[y][x]='0'; ex=x;ey=y;}
		dist[y][x]=99999999;
	}
	
	dist[ey][ex]=0;
	queue<int> Q;
	Q.push(ey*10000+ex);
	while(!Q.empty()) {
		int k=Q.front();
		Q.pop();
		int cx=k%10000,cy=k/10000;
		
		FOR(r,4) {
			int dx[4]={0,0,-1,1};
			int dy[4]={-1,1,0,0};
			int tx=cx+dx[r];
			int ty=cy+dy[r];
			if(tx<0 || tx>=W || ty<0 || ty>=H || S[ty][tx]=='T') continue;
			
			if(dist[ty][tx]>dist[cy][cx]+1) {
				dist[ty][tx]=dist[cy][cx]+1;
				Q.push(ty*10000+tx);
			}
		}
	}
	
	l=0;
	FOR(y,H) FOR(x,W) if(dist[y][x]<=dist[sy][sx] && S[y][x]>'0' && S[y][x]<='9') l+=S[y][x]-'0';
	_P("%d\n",l);
}

まとめ

ゴールに近い敵は結局避けられない、ということに気づくと簡単だね。