[ABC241] F - Skate

[Q] https://atcoder.jp/contests/abc241/tasks/abc241_f

やってることはシンプルだが、重たい実装になってしまった。

1. 座標圧縮したい。石の他に、石の上下左右のx,y座標も考慮すべき。N*10要素すべてで座標圧縮。
2. 石の位置をx座標基準で保管するset[x] = yと、y座標基準で保管するset[y] = xを用意。
3. BFS。lower_boundで上下左右へ移動地点を探す。

実装

// 座標圧縮
template <typename T>
ll comp(vector<T> &A) {
 map<T, ll> mp;
 for (auto p : A) mp[p] = 0;
 ll sz = 0;
 for (auto &p : mp) p.second = ++sz;
 for (auto &a : A) a = mp[a];
 return sz;
}
ll dx[] = {0, 1, 0, -1};
ll dy[] = {-1, 0, 1, 0};

----------------------------------------------------------------------
ll H, W, N;
ll sx, sy, gx, gy;

set<ll> yoko[1000010];  // yoko[h]
set<ll> tate[1000010];  // tate[x]

int main() {
 cincout();

 cin >> H >> W >> N;
 cin >> sy >> sx >> gy >> gx;
// 座標圧縮したいので、石と、上下左右のマスを要素に入れる
 vector<ll> elm;
 elm.reserve(N * 10);
 rep(i, N) {
   ll x, y;
   cin >> y >> x;
   elm.push_back(y);
   elm.push_back(x);
   rep(j, 4) {
     ll ny = y + dy[j];
     ll nx = x + dx[j];
     elm.push_back(ny);
     elm.push_back(nx);
   }
 }
 elm.push_back(sy);
 elm.push_back(sx);
 elm.push_back(gy);
 elm.push_back(gx);
 ll ret = comp(elm);

 // m,u,r,d,l*2ずつ stoneだけいれる
 rep(i, N) {
   ll ny = elm[10 * i];
   ll nx = elm[10 * i + 1];
   yoko[ny].insert(nx);
   tate[nx].insert(ny);
 }
 sy = elm[N * 10];
 sx = elm[N * 10 + 1];
 gy = elm[N * 10 + 2];
 gx = elm[N * 10 + 3];

 // bfs
 queue<pll> Q;
 map<pll, bool> seen;  // N*Nになっちゃう？
 Q.push({sy, sx});
 seen[{sy, sx}] = true;

 ll turn = -1;
 while (!Q.empty()) {
   ll qsz = Q.size();
   ++turn;
   rep(i, qsz) {
     auto &[y, x] = Q.front();
     if (y == gy && x == gx) {
       cout << turn << endl;
       return 0;
     }
     // 今いる地点から、tateの直近2か所
     {
       auto it = tate[x].upper_bound(y);
       // 下にいけるか
       if (it != tate[x].end()) {
         ll ny = *it - 1;
         if (seen.count({ny, x}) == false) {
           seen[{ny, x}] = true;
           Q.push({ny, x});
         }
       }
       // 上にいけるか
       if (it != tate[x].begin()) {
         --it;
         ll ny = *it + 1;
         if (seen.count({ny, x}) == 0) {
           seen[{ny, x}] = true;
           Q.push({ny, x});
         }
       }
     }

     // 今いる地点から、yokoの直近2か所
     {
       auto it = yoko[y].upper_bound(x);
       // 右にいけるか
       if (it != yoko[y].end()) {
         ll nx = *it - 1;
         if (seen.count({y, nx}) == 0) {
           seen[{y, nx}] = true;
           Q.push({y, nx});
         }
       }
       // 左にいけるか
       if (it != yoko[y].begin()) {
         --it;
         ll nx = *it + 1;
         if (seen.count({y, nx}) == 0) {
           seen[{y, nx}] = true;
           Q.push({y, nx});
         }
       }
     }
     Q.pop();
   }
 }
 cout << -1 << endl;
}