Codeforces #229 Div2. D. Inna and Sweet Matrix

出力形式が変わった問題。
http://codeforces.com/contest/390/problem/D

問題

NxMの２次元グリッド上にK個の飴を配置したい。
初期状態では飴は配置されていない。

飴を(x,y)に置く時、以下の条件を満たすように置かなければならない。

• すでに飴があるマスは移動できないし、２個以上の飴を置くことはできない。
• (1,1)から（飴があるマス以外の）隣接マスをたどって(x,y)に移動しなければならない。その時、通過したマスが必要コストとなる。
• 飴を置いた後は自動的に(1,1)にジャンプする。

K個飴を配置する最少コストと、その手順を答えよ。

解法

(1,1)からマンハッタン距離が近い順にK個マスを選択し、遠い順に飴を置いていくだけ。
本番、DFSを行っているコードも見受けられたがそんな複雑な処理は不要。

int H,W,K;

void solve() {
	int f,i,j,k,l,x,y;
	cin>>H>>W>>K;
	
	int r=0;
	vector<pair<int,int> > V;
	for(l=1;l<=H+W-1;l++) {
		for(y=0;y<H;y++) {
			int x=(l-1)-y;
			if(x<0 || x>=W) continue;
			if(K--==0) goto out;
			r+=l;
			V.push_back(make_pair(x,y));
		}
	}
	out:
	_P("%d\n",r);
	FOR(i,V.size()) {
		int tx = V[V.size()-1-i].first+1;
		int ty = V[V.size()-1-i].second+1;
		x=1;y=1;
		
		while(y<ty) _P("(%d,%d) ",y,x), y++;
		while(x<=tx) _P("(%d,%d) ",y,x), x++;
		_P("\n");
	}
}

まとめ

本番は出力順を間違えて1WA…。