天下一プログラマ2014予選A E - パズルの移動

問題

日本語なので本文参照（http://tenka1-2014-quala.contest.atcoder.jp/tasks/tenka1_2014_qualA_e）

制約条件

h≦20000
w≦16

方針

scc + DAG上のDP.

まずブロックに適当にIDを割り振る。
で、どのブロックを押すと次にどのブロックが一緒に動くかのグラフを作る。
このグラフはループを含むので、強連結成分分解してDAGにする。

DAGのそれぞれの頂点ごとに、x座標ごとにどのy座標までのブロックが一緒に落ちるかを持たせる。
(dp[c][i] := cの成分を落としたときに、x座標iにおいて落ちるyの最小値）
これを更新していくDPをすればよい。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int h, w;
int memo[20000 * 16], dp[20000 * 16][16];
char in[20000][17];

int p[20000 * 16];
inline int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}
inline int rec(int c, const Graph &g, const vector<vi> &block){
	int &res = memo[c];
	if(res >= 0) return res;
	
	rep(i, block[c].size()) dp[c][block[c][i] % w] = min(dp[c][block[c][i] % w], block[c][i] / w);
	
	each(i, g[c]) if(i->dst != c){
		rec(i->dst, g, block);
		rep(j, w) dp[c][j] = min(dp[c][j], dp[i->dst][j]);
	}
	res = 0;
	rep(j, w) res += h - min(h, dp[c][j]);
	return res;
}

int main(){
	memset(memo, -1, sizeof(memo));
	
	scanf("%d%d", &h, &w);
	rep(i, h) scanf("%s", in[i]);
	
	rep(i, h) rep(j, w){
		p[i * w + j] = i * w + j;
		rep(k, w) dp[i * w + j][k] = inf;
	}
	rep(i, h) rep(j, w) rep(d, 2){
		int ny = i + dy[d], nx = j + dx[d];
		if(ny < 0 || nx < 0 || ny >= h || nx >= w || in[i][j] != in[ny][nx]) continue;
		int a = root(i * w + j), b = root(ny * w + nx);
		if(a != b) p[b] = a;
	}
	
	Graph g(h * w);
	vector<vi> scc;
	
	rep(i, h - 1) rep(j, w){
		int r = root(i * w + j), r2 = root((i + 1) * w + j);
		if(r != r2) g[r].pb(Edge(r, r2, 0));
	}
	stronglyConnectedComponents(g, scc);
	
	int m = scc.size();
	map<int, int> to;
	vector<vi> block(m);
	Graph e(m);
	rep(i, m) rep(j, scc[i].size())to[scc[i][j]] = i;
	rep(i, h) rep(j, w) block[to[root(i * w + j)]].pb(i * w + j);
	rep(i, g.size()) rep(j, g[i].size()) e[to[i]].pb(Edge(to[i], to[g[i][j].dst], 0));
	
	int q;
	scanf("%d", &q);
	while(q--){
		int y, x; scanf("%d%d", &x, &y); x--; y--;
		int r = to[root(y * w + x)];
		printf("%d\n", rec(r, e, block));
	}
	return 0;
}