毒の沼地 [ICPC JAG 模擬国内予選 2019 B]

問題文と入出力

前提知識

• 01-BFS

解説

今回の問題は、
damage(sx, sy, tx, ty) := 座標(sx,sy)から座標(tx, ty)へ移るための最小ダメージ
として、damage(X[0], Y[0], X[1], Y[1]) + damage(X[1], Y[1], X[2], Y[2]) + ...をしていけばいい。
　
damage関数の中身は、最短経路問題を解くことになる。
移動先が毒であればコスト1, 移動先が毒でないならコスト0の最短経路問題なので、
これは01-BFSである。
01-BFSはO(状態数)で計算ができるので、これで解こう。
　
ICPCは実行時間にそんなに厳しくないので、01-BFSがもし分からなくても、
ダイクストラでも待っていればACできる。

int N, A, B, C, D, X[101], Y[101];
//---------------------------------------------------------------------------------------------------
bool isSafe(int x, int y) {
	return A <= x and x <= C and B <= y and y <= D;
}
bool vis[101][101];
int dst[101][101];
int damage(int sx, int sy, int tx, int ty) {
	rep(x, 0, 101) rep(y, 0, 101) vis[y][x] = false;
	rep(x, 0, 101) rep(y, 0, 101) dst[y][x] = inf;

	deque<pair<int,int>> que;
	que.push_back({ sx, sy });
	dst[sy][sx] = 0;

	while (!que.empty()) {
		int x, y;
		tie(x, y) = que.front();
		que.pop_front();

		if (x == tx and y == ty) return dst[y][x];

		if (vis[y][x]) continue;
		vis[y][x] = true;

		rep(d, 0, 4) {
			int xx = x + dx[d];
			int yy = y + dy[d];
			if (1 <= xx and xx <= 100 and 1 <= yy and yy <= 100 and !vis[yy][xx]) {
				int cst2 = dst[y][x];
				if (isSafe(xx, yy)) {
					if (chmin(dst[yy][xx], dst[y][x])) que.push_front({xx, yy});
				}
				else {
					if (chmin(dst[yy][xx], dst[y][x] + 1)) que.push_back({ xx, yy });
				}
			}
		}
	}

	assert(0);
	return -1;
}
//---------------------------------------------------------------------------------------------------
void solve() {
	int x = X[0], y = Y[0];
	int ans = 0;
	rep(i, 1, N + 1) {
		ans += damage(x, y, X[i], Y[i]);
		x = X[i];
		y = Y[i];
	}
	cout << ans << endl;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	while (cin >> N) {
		if (N == 0) return;
		cin >> A >> B >> C >> D;
		rep(i, 0, N + 1) cin >> X[i] >> Y[i];
		solve();
	}
}