https://atcoder.jp/contests/otemae2019/tasks/otemae2019_g
前提知識
解説
https://atcoder.jp/contests/otemae2019/submissions/6932829
ベースはBFSな感じがする。
だが、BFSにしては盤面が広い。
そこで座標圧縮してダイクストラするという流れがある。
座標移動系で重要な座標は限られて、座標圧縮するとダイクストラできるという問題を見たことがある。
今回もそれベースで考えてみる。
よくよく見ると、ワープ可能範囲が矩形であるが、おそらく重要なのは、4隅だけであろう。
なので、始点終点と矩形の4隅で使われているx座標, y座標で座圧しよう。
これで各頂点について4辺ができて、コストもわかる。
あとは、場所によってコストが0になっているので、そこを判定すればいい。
これは、ある矩形について、コストが0になる部分も矩形の形になる。
矩形の部分すべてに+1するよう2Dimosを使えば、コストが0である部分を前計算できる。
これで頂点と辺が整ったので、あとはダイクストラする。
O(M2logM)で心配だが、よくよくみると実行時間も長めなので、気を付けて実装すれば通る。
int N, M, P, Q, R, S, T[1010], A[1010], B[1010], C[1010], D[1010]; //--------------------------------------------------------------------------------------------------- vector<int> dicx, dicy; int W, H; void compress() { dicx.push_back(P); dicy.push_back(Q); dicx.push_back(R); dicy.push_back(S); rep(i, 0, M) { dicx.push_back(A[i]); dicx.push_back(B[i]); dicy.push_back(C[i]); dicy.push_back(D[i]); } sort(all(dicx)); dicx.erase(unique(all(dicx)), dicx.end()); sort(all(dicy)); dicy.erase(unique(all(dicy)), dicy.end()); W = dicx.size(); H = dicy.size(); } //--------------------------------------------------------------------------------------------------- int warp_migi[2010][2010]; int warp_shita[2010][2010]; void makeEdges() { rep(i, 0, M) { int a = lower_bound(all(dicx), A[i]) - dicx.begin(); int b = lower_bound(all(dicx), B[i]) - dicx.begin(); int c = lower_bound(all(dicy), C[i]) - dicy.begin(); int d = lower_bound(all(dicy), D[i]) - dicy.begin(); if (T[i] == 1) { // tate warp warp_shita[a][c]++; warp_shita[b + 1][c]--; warp_shita[a][d]--; warp_shita[b + 1][d]++; } else { // yoko warp warp_migi[a][c]++; warp_migi[b][c]--; warp_migi[a][d + 1]--; warp_migi[b][d + 1]++; } } rep(x, 0, W) rep(y, 1, H) warp_migi[x][y] += warp_migi[x][y - 1]; rep(y, 0, H) rep(x, 1, W) warp_migi[x][y] += warp_migi[x - 1][y]; rep(x, 0, W) rep(y, 1, H) warp_shita[x][y] += warp_shita[x][y - 1]; rep(y, 0, H) rep(x, 1, W) warp_shita[x][y] += warp_shita[x - 1][y]; } //--------------------------------------------------------------------------------------------------- bool vis[2010][2010]; ll dist[2010][2010]; int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 }; ll dijk() { rep(y, 0, H) rep(x, 0, W) dist[x][y] = infl; rep(y, 0, H) rep(x, 0, W) vis[x][y] = false; min_priority_queue<pair<ll, pair<int,int>>> que; int sx = lower_bound(all(dicx), P) - dicx.begin(); int sy = lower_bound(all(dicy), Q) - dicy.begin(); int tx = lower_bound(all(dicx), R) - dicx.begin(); int ty = lower_bound(all(dicy), S) - dicy.begin(); dist[sx][sy] = 0; que.push({ 0, {sx, sy} }); while (!que.empty()) { auto q = que.top(); que.pop(); ll cst = q.first; int x = q.second.first; int y = q.second.second; if (vis[x][y]) continue; vis[x][y] = true; if (x == tx and y == ty) return dist[x][y]; rep(d, 0, 4) { int xx = x + dx[d]; int yy = y + dy[d]; if (0 <= xx and xx < W and 0 <= yy and yy < H) { ll cst = 0; if (d % 2 == 0) { // tate if (warp_shita[x][min(y, yy)] == 0) cst = dicy[max(y, yy)] - dicy[min(y, yy)]; } else { // yoko if (warp_migi[min(x, xx)][y] == 0) cst = dicx[max(x, xx)] - dicx[min(x, xx)]; } if (chmin(dist[xx][yy], dist[x][y] + cst)) { que.push({ dist[xx][yy], {xx, yy} }); } } } } return -1; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M >> P >> Q >> R >> S; rep(i, 0, M) cin >> T[i] >> A[i] >> B[i] >> C[i] >> D[i]; compress(); makeEdges(); cout << dijk() << endl; }
