Codeforces #203 Div2. C. Bombs

CF203はDiv2 onlyなので練習のみ。
http://codeforces.com/contest/350/problem/C

問題

２次元座標上でいくつか地雷が埋められたマスがある。
ここで、地雷撤去ロボを使って地雷を取り除きたい。
ロボは初期状態で原点におり、地雷を持たない。
ロボは以下の動きのいずれかを取れる。

• 上下左右のいずれかに何マスか移動する。ただし、地雷があるマスを始点として移動することはできない。
• 足元に地雷があり、かつロボが地雷を持たない場合、地雷を持ち上げる。
• ロボが原点にいる場合、地雷を置く。

全部の地雷を撤去するまでの処理回数を最小化し、そのステップを示せ。

解法

地雷マスまで移動して地雷を持ち、原点に戻って地雷を置く、という処理を繰り返す。
地雷がX軸またはY軸上なら原点から１回の移動で到達でき、そうでなければ２回の移動が必要。
よって、軸上の地雷は４ステップ、それ以外は６ステップで処理できる。

移動中、地雷を持った状態で他の地雷マスで曲がることはできないので、マンハッタン距離が原点に近い順に処理すればよい。

int N,X[100001],Y[100001];
pair<int,int> P[1000001];

void solve() {
	int f,i,j,k,l, x,y,r=0;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		X[i]=x;Y[i]=y;
		P[i]=make_pair(abs(x)+abs(y),i);
		if(x==0 || y==0) r+=4;
		else r+=6;
	}
	sort(P,P+N);
	_P("%d\n",r);
	FOR(i,N) {
		j=P[i].second;
		if(X[j]<0) _P("1 %d L\n",-X[j]);
		if(X[j]>0) _P("1 %d R\n", X[j]);
		if(Y[j]<0) _P("1 %d D\n",-Y[j]);
		if(Y[j]>0) _P("1 %d U\n", Y[j]);
		_P("2\n");
		if(X[j]<0) _P("1 %d R\n",-X[j]);
		if(X[j]>0) _P("1 %d L\n", X[j]);
		if(Y[j]<0) _P("1 %d U\n",-Y[j]);
		if(Y[j]>0) _P("1 %d D\n", Y[j]);
		_P("3\n");
	}
}

まとめ

ここらへんはまだ簡単。