Codeforces #224 Div2. D. Ksenia and Pawns

これはすんなりアプローチを思いついた。
http://codeforces.com/contest/382/problem/D

問題

２次元のグリッドが与えられる。
各セルは、４方向の矢印のいずれかが書かれているか、何も書かれていない。

グリッド上、２つの異なるマスに駒を置くことを考える。
各駒は、矢印マスに乗っている場合、時間を１かけて矢印の方向のマスに移動し、矢印のないマスに到達したら移動終了である。

２つの駒を最適なマスに配置したとき、２つの駒の合計移動可能時間を最大化せよ。
ただし、２つの駒は矢印マス上で同じマスに同じタイミングで乗ってはならない。

解法

まず、各マスに駒を配置した際、矢印のないマスに到達するまでの移動時間を求める。
これは普通にDFSすればよい。
また、矢印のないマスに到達できないマスがある場合、そこを開始位置にすれば無限時間移動できる。

次に移動時間が最大となるマスを２つ選択するわけだが、同じ矢印マスを共有できないという条件を考慮する必要がある。
これは、各マスについて矢印のないマスに到達する直前のマスを覚えておけばよい。
直前マスを共有し、かつ移動時間の同じマスを２つ選択すると、直前マスまでに同じマスに重なるので不可となる。

移動時間が最大となるマスを列挙し、それぞれの直前マスの集合を取って集合が２要素以上なら、移動時間最大マスを２個選択可能。
１要素しかないなら、１つは移動時間最大、２つ目は移動時間最大-1のマスを選択する。

int H,W;
string S[2001];
pair<int,int> P[2001][2001];
int D[2001][2001];

void solve() {
	int f,i,j,k,l,x,y,ma=0;
	
	MINUS(P);
	MINUS(D);
	
	queue<pair<int,int> > Q;
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) if(S[y][x]=='#') D[y][x]=0,P[y][x]=make_pair(x,y),Q.push(make_pair(x,y));
	}
	
	while(!Q.empty()) {
		int cx=Q.front().first;
		int cy=Q.front().second;
		Q.pop();
		
		FOR(i,4) {
			int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
			int ty=cy+dy[i],tx=cx+dx[i];
			if(tx<0 || tx>=W || ty<0 || ty>=H) continue;
			if(D[ty][tx]!=-1) continue;
			if(i==0 && S[ty][tx]!='<') continue;
			if(i==1 && S[ty][tx]!='>') continue;
			if(i==2 && S[ty][tx]!='^') continue;
			if(i==3 && S[ty][tx]!='v') continue;
			D[ty][tx]=D[cy][cx]+1;
			if(D[ty][tx]==1) P[ty][tx]=make_pair(tx,ty);
			else P[ty][tx]=P[cy][cx];
			Q.push(make_pair(tx,ty));
			ma=max(ma,D[ty][tx]);
		}
	}
	
	FOR(y,H) FOR(x,W) if(D[y][x]==-1) return _P("-1\n");
	if(ma==0) return _P("0\n");
	set<pair<int,int> > S;
	FOR(y,H) FOR(x,W) if(D[y][x]==ma) S.insert(P[y][x]);
	
	_P("%d\n",2*ma-(S.size()==1));
}

まとめ

これはすんなり。