雪の足跡 [yukicoder 340]

問題

https://yukicoder.me/problems/no/340

W×Hの盤面があり、N人の人がそこを通る。
i番目の人はM[i]回移動していて、移動先はB[i][j]->B[i][j + 1]である。
移動元と移動先はw + h * Wで表記されていて、距離が1とは限らない。

その移動後に(0,0)から(W - 1, H - 1)へN人が移動した方向と同じ方向に移れるとしたときの最短距離を求めよ。

1 <= W, H <= 10^3
0 <= N, M[i] <= 10^3
0 <= B[i][j] < W * H

解説

この問題は

1. 移動した人から辺を作る
2. 作った辺上でBFSして最短距離を求める

ことから解きます。

普通に辺を作ると、O(W*H*len) : len移動距離の最大値かかりますが、こういうデータ構造を使って処理します。

• 区間[a,b]を追加する（マージできる区間があればする）
• 頂点a, bが同じ区間に属するか判定する

これを以下のように実装しました

#define INF INT_MAX/2
struct SectionStructure {
	set<pair<int, int>> buf;
	SectionStructure() {
		buf.insert({ -INF, -INF });
		buf.insert({ INF , INF });
	}
	void add(int l, int r) {
		auto ite = buf.lower_bound({ l, -INF });

		if (ite->first == INF) { // 大きいやつが無い
			ite--;
			if (ite->second <= l) { // 被ってないなら追加
				buf.insert({ l, r });
			}
			else { // 被ってるならそれとくっつける
				int L = ite->first;
				int R = ite->second;

				buf.erase(ite);
				buf.insert({ L, max(r, R) });
			}
		}
		else { // 被ってるのがある
			auto pre = buf.upper_bound({ r, -INF });
			auto pp = pre;
			pp--;

			int L = min(l, ite->first);
			int R = max(r, pp->second);

			buf.erase(ite, pre);
			buf.insert({ L, R });
		}
	}
	int check(int a, int b) {
		if (a > b) swap(a, b);
		auto aa = buf.upper_bound({ a, INF });
		aa--;
		if (aa->first == -INF) return false;
		return b <= aa->second;
	}
	void print() {
		printf("<>\n");
		for (auto p : buf) printf("[%d,%d]\n", p.first, p.second);
	}
};

注意なのですが、今回の問題の性質上、[1,2]と[2,3]のように端だけ被ってる場合はマージしていません。
これを使って後は解くだけです。

https://yukicoder.me/submissions/153272

• makeEdge() で辺を張って
• bfs() で最短距離を計算

しています。