kmjp's blog

競技プログラミング参加記です

Codeforces #224 Div2. D. Ksenia and Pawns

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

問題

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

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

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

解法

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

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

移動時間が最大となるマスを列挙し、それぞれの直前マスの集合を取って集合が2要素以上なら、移動時間最大マスを2個選択可能。
1要素しかないなら、1つは移動時間最大、2つ目は移動時間最大-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));
}

まとめ

これはすんなり。