other/sliding_puzzle_solver.hpp

• View this file on GitHub
• Last update: 2024-07-23 21:27:24+09:00
• Include: #include "other/sliding_puzzle_solver.hpp"

Depends on

• alg/monoid/add.hpp
• ds/fenwicktree/fenwicktree.hpp
• ds/fenwicktree/fenwicktree_01.hpp
• linalg/transpose.hpp
• seq/inversion.hpp

Code

#include "linalg/transpose.hpp"
#include "seq/inversion.hpp"

/*
O(HW(H+W))
空マスは -1 (unique)
同じ値が複数あってもよい
操作回数を K として、長さ K+1 の空マスの座標列をかえす
*/
struct Slinding_Puzzle_Solver {
  using P = pair<int, int>;
  vc<P> solve(vvc<int> A, vvc<int> B) {
    int H = len(A), W = len(A[0]);
    auto find = [&](vvc<int>& A, int k) -> P {
      FOR(x, H) FOR(y, W) if (A[x][y] == k) return {x, y};
      assert(0);
    };
    auto [ax, ay] = find(A, -1);
    auto [bx, by] = find(B, -1);
    vc<P> ANS_1, ANS_2;
    while (ax > 0) { ANS_1.eb(ax, ay), swap(A[ax][ay], A[ax - 1][ay]), --ax; }
    while (ay > 0) { ANS_1.eb(ax, ay), swap(A[ax][ay], A[ax][ay - 1]), --ay; }
    while (bx > 0) { ANS_2.eb(bx, by), swap(B[bx][by], B[bx - 1][by]), --bx; }
    while (by > 0) { ANS_2.eb(bx, by), swap(B[bx][by], B[bx][by - 1]), --by; }
    vc<P> ANS = solve_00(A, B);
    if (ANS.empty()) return {};
    reverse(all(ANS_2));
    return concat(ANS_1, ANS, ANS_2);
  }

private:
  vc<P> solve_00(vvc<int> A, vvc<int> B) {
    assert(A[0][0] == -1 && B[0][0] == -1);
    int H = len(A), W = len(A[0]);
    if (H == 1 || W == 1) {
      if (A != B) return {};
      vc<P> ANS;
      ANS.eb(0, 0);
      return ANS;
    }
    vc<P> XYA, XYB;
    FOR(x, H) FOR(y, W) XYA.eb(x, y), XYB.eb(x, y);
    sort(all(XYA), [&](auto& a, auto& b) -> bool {
      return A[a.fi][a.se] < A[b.fi][b.se];
    });
    sort(all(XYB), [&](auto& a, auto& b) -> bool {
      return B[a.fi][a.se] < B[b.fi][b.se];
    });
    auto check = [&]() -> bool {
      vc<int> S, T;
      FOR(i, H * W) {
        auto [x1, y1] = XYA[i];
        auto [x2, y2] = XYB[i];
        if (A[x1][y1] != B[x2][y2]) return 0;
        S.eb(W * x1 + y1);
        T.eb(W * x2 + y2);
      }
      ll x = inversion_between(S, T);
      return x % 2 == 0;
    };
    if (!check()) {
      FOR(i, H * W - 1) {
        auto [x1, y1] = XYA[i];
        auto [x2, y2] = XYA[i + 1];
        if (A[x1][y1] != A[x2][y2]) continue;
        swap(XYA[i], XYA[i + 1]);
        break;
      }
      if (!check()) return {};
    }
    vv(P, X, H, W);
    FOR(i, H * W) {
      auto [x1, y1] = XYA[i];
      auto [x2, y2] = XYB[i];
      X[x1][y1] = {x2, y2};
    }
    vc<P> ANS;
    ANS.eb(0, 0);
    solve_sort(X, ANS, false);
    return ANS;
  }

  // 移動先の座標の列を並べたグリッドを与える.
  // (0,0) が空マス
  void solve_sort(vvc<pair<int, int>>& A, vc<P>& ANS, bool tr) {
    int H = len(A), W = len(A[0]);
    vv(P, pos, H, W);
    FOR(x, H) FOR(y, W) {
      P p = A[x][y];
      pos[p.fi][p.se] = {x, y};
    }

    auto [px, py] = pos[0][0];

    auto ope = [&](int x, int y) -> void {
      assert(abs(px - x) + abs(py - y) == 1);
      swap(A[px][py], A[x][y]);
      if (!tr) ANS.eb(x, y);
      if (tr) ANS.eb(y, x);
      pos[A[px][py].fi][A[px][py].se] = {px, py};
      px = x, py = y;
      pos[A[px][py].fi][A[px][py].se] = {px, py};
    };
    if (H == 2 && W == 2) {
      auto check = [&]() -> bool {
        FOR(x, H) FOR(y, W) if (A[x][y].fi != x || A[x][y].se != y) return 0;
        return 1;
      };
      while (!check()) {
        if (px == 0 && py == 0) ope(1, 0);
        if (px == 1 && py == 0) ope(1, 1);
        if (px == 1 && py == 1) ope(0, 1);
        if (px == 0 && py == 1) ope(0, 0);
      }
      return;
    }
    if (H < W) {
      FOR(x, H) FOR(y, W) { swap(A[x][y].fi, A[x][y].se); }
      A = transpose(A, H, W);
      solve_sort(A, ANS, !tr);
      return;
    }
    assert(H >= 3 && W >= 2);
    // 最後の行をそろえる
    FOR_R(y, 1, W) {
      auto& [tx, ty] = pos[H - 1][y];
      if (px == H - 1) ope(px - 1, py);
      while (px - 1 > tx) ope(px - 1, py), tie(tx, ty) = pos[H - 1][y];
      while (px + 1 < tx) ope(px + 1, py), tie(tx, ty) = pos[H - 1][y];
      if (px == tx) {
        if (px == 0)
          ope(px + 1, py);
        else
          ope(px - 1, py);
      }
      assert(abs(px - tx) == 1);
      while (py < ty) ope(px, py + 1);
      while (py > ty) ope(px, py - 1);
      if (px == tx + 1) ope(px - 1, py), tie(tx, ty) = pos[H - 1][y];
      assert(px == tx - 1 && py == ty);
      while (ty < y) {
        ope(px, py + 1), ope(px + 1, py), ope(px, py - 1), ope(px - 1, py),
            ope(px, py + 1);
      }
      while (ty > y) {
        ope(px, py - 1), ope(px + 1, py), ope(px, py + 1), ope(px - 1, py),
            ope(px, py - 1);
      }
      tie(tx, ty) = pos[H - 1][y];
      while (tx < H - 1) {
        ope(px, py - 1), ope(px + 1, py), ope(px + 1, py), ope(px, py + 1),
            ope(px - 1, py);
        tie(tx, ty) = pos[H - 1][y];
      }
      assert(A[H - 1][y] == (pair<int, int>{H - 1, y}));
    }
    auto& [tx, ty] = pos[H - 1][0];
    if (px == H - 1) ope(px - 1, py);
    while (px - 1 > tx) ope(px - 1, py), tie(tx, ty) = pos[H - 1][0];
    while (px + 1 < tx) ope(px + 1, py), tie(tx, ty) = pos[H - 1][0];
    if (px == tx) {
      if (px == 0)
        ope(px + 1, py);
      else
        ope(px - 1, py);
    }
    tie(tx, ty) = pos[H - 1][0];
    assert(abs(px - tx) == 1);
    while (py < ty) ope(px, py + 1);
    while (py > ty) ope(px, py - 1);
    if (px == tx + 1) ope(px - 1, py);
    tie(tx, ty) = pos[H - 1][0];
    if (tx < H - 1) {
      assert(px == tx - 1 && py == ty);
      while (ty > 0) {
        ope(px, py - 1), ope(px + 1, py), ope(px, py + 1), ope(px - 1, py),
            ope(px, py - 1);
      }
      tie(tx, ty) = pos[H - 1][0];
      while (tx < H - 2) {
        ope(px, py + 1), ope(px + 1, py), ope(px + 1, py), ope(px, py - 1),
            ope(px - 1, py);
      }
      ope(px + 1, py), ope(px + 1, py), ope(px, py + 1);
      ope(px - 1, py), ope(px, py - 1), ope(px - 1, py);
      ope(px, py + 1), ope(px + 1, py), ope(px + 1, py);
      ope(px, py - 1), ope(px - 1, py);
    }
    FOR(y, W) assert(A[H - 1][y] == (pair<int, int>{H - 1, y}));
    POP(A);
    solve_sort(A, ANS, tr);
  }
};

#line 1 "linalg/transpose.hpp"
template <typename VC>
vc<VC> transpose(const vc<VC>& A, int H = -1, int W = -1) {
  if (H == -1) { H = len(A), W = len(A[0]); }
  vc<VC> B(W, VC(H, A[0][0]));
  FOR(x, H) FOR(y, W) B[y][x] = A[x][y];
  return B;
}
#line 2 "ds/fenwicktree/fenwicktree_01.hpp"

#line 2 "alg/monoid/add.hpp"

template <typename E>
struct Monoid_Add {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 3 "ds/fenwicktree/fenwicktree.hpp"

template <typename Monoid>
struct FenwickTree {
  using G = Monoid;
  using MX = Monoid;
  using E = typename G::value_type;
  int n;
  vector<E> dat;
  E total;

  FenwickTree() {}
  FenwickTree(int n) { build(n); }
  template <typename F>
  FenwickTree(int n, F f) {
    build(n, f);
  }
  FenwickTree(const vc<E>& v) { build(v); }

  void build(int m) {
    n = m;
    dat.assign(m, G::unit());
    total = G::unit();
  }
  void build(const vc<E>& v) {
    build(len(v), [&](int i) -> E { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m;
    dat.clear();
    dat.reserve(n);
    total = G::unit();
    FOR(i, n) { dat.eb(f(i)); }
    for (int i = 1; i <= n; ++i) {
      int j = i + (i & -i);
      if (j <= n) dat[j - 1] = G::op(dat[i - 1], dat[j - 1]);
    }
    total = prefix_sum(m);
  }

  E prod_all() { return total; }
  E sum_all() { return total; }
  E sum(int k) { return prefix_sum(k); }
  E prod(int k) { return prefix_prod(k); }
  E prefix_sum(int k) { return prefix_prod(k); }
  E prefix_prod(int k) {
    chmin(k, n);
    E ret = G::unit();
    for (; k > 0; k -= k & -k) ret = G::op(ret, dat[k - 1]);
    return ret;
  }
  E sum(int L, int R) { return prod(L, R); }
  E prod(int L, int R) {
    chmax(L, 0), chmin(R, n);
    if (L == 0) return prefix_prod(R);
    assert(0 <= L && L <= R && R <= n);
    E pos = G::unit(), neg = G::unit();
    while (L < R) { pos = G::op(pos, dat[R - 1]), R -= R & -R; }
    while (R < L) { neg = G::op(neg, dat[L - 1]), L -= L & -L; }
    return G::op(pos, G::inverse(neg));
  }

  vc<E> get_all() {
    vc<E> res(n);
    FOR(i, n) res[i] = prod(i, i + 1);
    return res;
  }

  void add(int k, E x) { multiply(k, x); }
  void multiply(int k, E x) {
    static_assert(G::commute);
    total = G::op(total, x);
    for (++k; k <= n; k += k & -k) dat[k - 1] = G::op(dat[k - 1], x);
  }

  template <class F>
  int max_right(const F check, int L = 0) {
    assert(check(G::unit()));
    E s = G::unit();
    int i = L;
    // 2^k 進むとダメ
    int k = [&]() {
      while (1) {
        if (i % 2 == 1) { s = G::op(s, G::inverse(dat[i - 1])), i -= 1; }
        if (i == 0) { return topbit(n) + 1; }
        int k = lowbit(i) - 1;
        if (i + (1 << k) > n) return k;
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (!check(t)) { return k; }
        s = G::op(s, G::inverse(dat[i - 1])), i -= i & -i;
      }
    }();
    while (k) {
      --k;
      if (i + (1 << k) - 1 < len(dat)) {
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (check(t)) { i += (1 << k), s = t; }
      }
    }
    return i;
  }

  // check(i, x)
  template <class F>
  int max_right_with_index(const F check, int L = 0) {
    assert(check(L, G::unit()));
    E s = G::unit();
    int i = L;
    // 2^k 進むとダメ
    int k = [&]() {
      while (1) {
        if (i % 2 == 1) { s = G::op(s, G::inverse(dat[i - 1])), i -= 1; }
        if (i == 0) { return topbit(n) + 1; }
        int k = lowbit(i) - 1;
        if (i + (1 << k) > n) return k;
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (!check(i + (1 << k), t)) { return k; }
        s = G::op(s, G::inverse(dat[i - 1])), i -= i & -i;
      }
    }();
    while (k) {
      --k;
      if (i + (1 << k) - 1 < len(dat)) {
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (check(i + (1 << k), t)) { i += (1 << k), s = t; }
      }
    }
    return i;
  }

  template <class F>
  int min_left(const F check, int R) {
    assert(check(G::unit()));
    E s = G::unit();
    int i = R;
    // false になるところまで戻る
    int k = 0;
    while (i > 0 && check(s)) {
      s = G::op(s, dat[i - 1]);
      k = lowbit(i);
      i -= i & -i;
    }
    if (check(s)) {
      assert(i == 0);
      return 0;
    }
    // 2^k 進むと ok になる
    // false を維持して進む
    while (k) {
      --k;
      E t = G::op(s, G::inverse(dat[i + (1 << k) - 1]));
      if (!check(t)) { i += (1 << k), s = t; }
    }
    return i + 1;
  }

  int kth(E k, int L = 0) {
    return max_right([&k](E x) -> bool { return x <= k; }, L);
  }
};
#line 4 "ds/fenwicktree/fenwicktree_01.hpp"

struct FenwickTree_01 {
  int N, n;
  vc<u64> dat;
  FenwickTree<Monoid_Add<int>> bit;
  FenwickTree_01() {}
  FenwickTree_01(int n) { build(n); }
  template <typename F>
  FenwickTree_01(int n, F f) {
    build(n, f);
  }

  void build(int m) {
    N = m;
    n = ceil<int>(N + 1, 64);
    dat.assign(n, u64(0));
    bit.build(n);
  }

  template <typename F>
  void build(int m, F f) {
    N = m;
    n = ceil<int>(N + 1, 64);
    dat.assign(n, u64(0));
    FOR(i, N) { dat[i / 64] |= u64(f(i)) << (i % 64); }
    bit.build(n, [&](int i) -> int { return popcnt(dat[i]); });
  }

  int sum_all() { return bit.sum_all(); }
  int sum(int k) { return prefix_sum(k); }
  int prefix_sum(int k) {
    int ans = bit.sum(k / 64);
    ans += popcnt(dat[k / 64] & ((u64(1) << (k % 64)) - 1));
    return ans;
  }
  int sum(int L, int R) {
    if (L == 0) return prefix_sum(R);
    int ans = 0;
    ans -= popcnt(dat[L / 64] & ((u64(1) << (L % 64)) - 1));
    ans += popcnt(dat[R / 64] & ((u64(1) << (R % 64)) - 1));
    ans += bit.sum(L / 64, R / 64);
    return ans;
  }

  void add(int k, int x) {
    if (x == 1) add(k);
    if (x == -1) remove(k);
  }

  void add(int k) {
    dat[k / 64] |= u64(1) << (k % 64);
    bit.add(k / 64, 1);
  }
  void remove(int k) {
    dat[k / 64] &= ~(u64(1) << (k % 64));
    bit.add(k / 64, -1);
  }

  int kth(int k, int L = 0) {
    if (k >= sum_all()) return N;
    k += popcnt(dat[L / 64] & ((u64(1) << (L % 64)) - 1));
    L /= 64;
    int mid = 0;
    auto check = [&](auto e) -> bool {
      if (e <= k) chmax(mid, e);
      return e <= k;
    };
    int idx = bit.max_right(check, L);
    if (idx == n) return N;
    k -= mid;
    u64 x = dat[idx];
    int p = popcnt(x);
    if (p <= k) return N;
    k = binary_search([&](int n) -> bool { return (p - popcnt(x >> n)) <= k; },
                      0, 64, 0);
    return 64 * idx + k;
  }

  int next(int k) {
    int idx = k / 64;
    k %= 64;
    u64 x = dat[idx] & ~((u64(1) << k) - 1);
    if (x) return 64 * idx + lowbit(x);
    idx = bit.kth(0, idx + 1);
    if (idx == n || !dat[idx]) return N;
    return 64 * idx + lowbit(dat[idx]);
  }

  int prev(int k) {
    if (k == N) --k;
    int idx = k / 64;
    k %= 64;
    u64 x = dat[idx];
    if (k < 63) x &= (u64(1) << (k + 1)) - 1;
    if (x) return 64 * idx + topbit(x);
    idx = bit.min_left([&](auto e) -> bool { return e <= 0; }, idx) - 1;
    if (idx == -1) return -1;
    return 64 * idx + topbit(dat[idx]);
  }
};
#line 3 "seq/inversion.hpp"

template <typename T>
ll inversion(vc<T> A) {
  int N = len(A);
  if (A.empty()) return 0;
  ll ANS = 0;
  FenwickTree_01 bit(N);
  auto I = argsort(A);
  for (auto& i: I) {
    ANS += bit.sum_all() - bit.sum(i);
    bit.add(i, 1);
  }
  return ANS;
}

// i 番目：A_i が先頭になるように rotate したときの転倒数
template <typename T, bool SMALL = false>
vi inversion_rotate(vc<T>& A) {
  const int N = len(A);
  if (!SMALL) {
    auto key = A;
    UNIQUE(key);
    for (auto&& x: A) x = LB(key, x);
  }
  ll K = MAX(A) + 1;
  ll ANS = 0;
  FenwickTree<Monoid_Add<int>> bit(K);
  for (auto&& x: A) {
    ANS += bit.sum(x + 1, K);
    bit.add(x, 1);
  }
  vi res(N);
  FOR(i, N) {
    res[i] = ANS;
    ll x = A[i];
    ANS = ANS + bit.sum(x + 1, K) - bit.prefix_sum(x);
  }
  return res;
}

// inv[i][j] = inversion A[i:j) であるような (N+1, N+1) テーブル
template <typename T>
vvc<int> all_range_inversion(vc<T>& A) {
  int N = len(A);
  vv(int, dp, N + 1, N + 1);
  FOR_R(L, N + 1) FOR(R, L + 2, N + 1) {
    dp[L][R] = dp[L][R - 1] + dp[L + 1][R] - dp[L + 1][R - 1];
    if (A[L] > A[R - 1]) ++dp[L][R];
  }
  return dp;
}

template <typename T>
ll inversion_between(vc<T> A, vc<T> B) {
  int N = len(A);
  map<T, vc<int>> MP;
  FOR(i, N) MP[B[i]].eb(i);
  vc<int> TO(N);
  FOR_R(i, N) {
    auto& I = MP[A[i]];
    if (I.empty()) return -1;
    TO[i] = POP(I);
  }
  return inversion(TO);
}
#line 3 "other/sliding_puzzle_solver.hpp"

/*
O(HW(H+W))
空マスは -1 (unique)
同じ値が複数あってもよい
操作回数を K として、長さ K+1 の空マスの座標列をかえす
*/
struct Slinding_Puzzle_Solver {
  using P = pair<int, int>;
  vc<P> solve(vvc<int> A, vvc<int> B) {
    int H = len(A), W = len(A[0]);
    auto find = [&](vvc<int>& A, int k) -> P {
      FOR(x, H) FOR(y, W) if (A[x][y] == k) return {x, y};
      assert(0);
    };
    auto [ax, ay] = find(A, -1);
    auto [bx, by] = find(B, -1);
    vc<P> ANS_1, ANS_2;
    while (ax > 0) { ANS_1.eb(ax, ay), swap(A[ax][ay], A[ax - 1][ay]), --ax; }
    while (ay > 0) { ANS_1.eb(ax, ay), swap(A[ax][ay], A[ax][ay - 1]), --ay; }
    while (bx > 0) { ANS_2.eb(bx, by), swap(B[bx][by], B[bx - 1][by]), --bx; }
    while (by > 0) { ANS_2.eb(bx, by), swap(B[bx][by], B[bx][by - 1]), --by; }
    vc<P> ANS = solve_00(A, B);
    if (ANS.empty()) return {};
    reverse(all(ANS_2));
    return concat(ANS_1, ANS, ANS_2);
  }

private:
  vc<P> solve_00(vvc<int> A, vvc<int> B) {
    assert(A[0][0] == -1 && B[0][0] == -1);
    int H = len(A), W = len(A[0]);
    if (H == 1 || W == 1) {
      if (A != B) return {};
      vc<P> ANS;
      ANS.eb(0, 0);
      return ANS;
    }
    vc<P> XYA, XYB;
    FOR(x, H) FOR(y, W) XYA.eb(x, y), XYB.eb(x, y);
    sort(all(XYA), [&](auto& a, auto& b) -> bool {
      return A[a.fi][a.se] < A[b.fi][b.se];
    });
    sort(all(XYB), [&](auto& a, auto& b) -> bool {
      return B[a.fi][a.se] < B[b.fi][b.se];
    });
    auto check = [&]() -> bool {
      vc<int> S, T;
      FOR(i, H * W) {
        auto [x1, y1] = XYA[i];
        auto [x2, y2] = XYB[i];
        if (A[x1][y1] != B[x2][y2]) return 0;
        S.eb(W * x1 + y1);
        T.eb(W * x2 + y2);
      }
      ll x = inversion_between(S, T);
      return x % 2 == 0;
    };
    if (!check()) {
      FOR(i, H * W - 1) {
        auto [x1, y1] = XYA[i];
        auto [x2, y2] = XYA[i + 1];
        if (A[x1][y1] != A[x2][y2]) continue;
        swap(XYA[i], XYA[i + 1]);
        break;
      }
      if (!check()) return {};
    }
    vv(P, X, H, W);
    FOR(i, H * W) {
      auto [x1, y1] = XYA[i];
      auto [x2, y2] = XYB[i];
      X[x1][y1] = {x2, y2};
    }
    vc<P> ANS;
    ANS.eb(0, 0);
    solve_sort(X, ANS, false);
    return ANS;
  }

  // 移動先の座標の列を並べたグリッドを与える.
  // (0,0) が空マス
  void solve_sort(vvc<pair<int, int>>& A, vc<P>& ANS, bool tr) {
    int H = len(A), W = len(A[0]);
    vv(P, pos, H, W);
    FOR(x, H) FOR(y, W) {
      P p = A[x][y];
      pos[p.fi][p.se] = {x, y};
    }

    auto [px, py] = pos[0][0];

    auto ope = [&](int x, int y) -> void {
      assert(abs(px - x) + abs(py - y) == 1);
      swap(A[px][py], A[x][y]);
      if (!tr) ANS.eb(x, y);
      if (tr) ANS.eb(y, x);
      pos[A[px][py].fi][A[px][py].se] = {px, py};
      px = x, py = y;
      pos[A[px][py].fi][A[px][py].se] = {px, py};
    };
    if (H == 2 && W == 2) {
      auto check = [&]() -> bool {
        FOR(x, H) FOR(y, W) if (A[x][y].fi != x || A[x][y].se != y) return 0;
        return 1;
      };
      while (!check()) {
        if (px == 0 && py == 0) ope(1, 0);
        if (px == 1 && py == 0) ope(1, 1);
        if (px == 1 && py == 1) ope(0, 1);
        if (px == 0 && py == 1) ope(0, 0);
      }
      return;
    }
    if (H < W) {
      FOR(x, H) FOR(y, W) { swap(A[x][y].fi, A[x][y].se); }
      A = transpose(A, H, W);
      solve_sort(A, ANS, !tr);
      return;
    }
    assert(H >= 3 && W >= 2);
    // 最後の行をそろえる
    FOR_R(y, 1, W) {
      auto& [tx, ty] = pos[H - 1][y];
      if (px == H - 1) ope(px - 1, py);
      while (px - 1 > tx) ope(px - 1, py), tie(tx, ty) = pos[H - 1][y];
      while (px + 1 < tx) ope(px + 1, py), tie(tx, ty) = pos[H - 1][y];
      if (px == tx) {
        if (px == 0)
          ope(px + 1, py);
        else
          ope(px - 1, py);
      }
      assert(abs(px - tx) == 1);
      while (py < ty) ope(px, py + 1);
      while (py > ty) ope(px, py - 1);
      if (px == tx + 1) ope(px - 1, py), tie(tx, ty) = pos[H - 1][y];
      assert(px == tx - 1 && py == ty);
      while (ty < y) {
        ope(px, py + 1), ope(px + 1, py), ope(px, py - 1), ope(px - 1, py),
            ope(px, py + 1);
      }
      while (ty > y) {
        ope(px, py - 1), ope(px + 1, py), ope(px, py + 1), ope(px - 1, py),
            ope(px, py - 1);
      }
      tie(tx, ty) = pos[H - 1][y];
      while (tx < H - 1) {
        ope(px, py - 1), ope(px + 1, py), ope(px + 1, py), ope(px, py + 1),
            ope(px - 1, py);
        tie(tx, ty) = pos[H - 1][y];
      }
      assert(A[H - 1][y] == (pair<int, int>{H - 1, y}));
    }
    auto& [tx, ty] = pos[H - 1][0];
    if (px == H - 1) ope(px - 1, py);
    while (px - 1 > tx) ope(px - 1, py), tie(tx, ty) = pos[H - 1][0];
    while (px + 1 < tx) ope(px + 1, py), tie(tx, ty) = pos[H - 1][0];
    if (px == tx) {
      if (px == 0)
        ope(px + 1, py);
      else
        ope(px - 1, py);
    }
    tie(tx, ty) = pos[H - 1][0];
    assert(abs(px - tx) == 1);
    while (py < ty) ope(px, py + 1);
    while (py > ty) ope(px, py - 1);
    if (px == tx + 1) ope(px - 1, py);
    tie(tx, ty) = pos[H - 1][0];
    if (tx < H - 1) {
      assert(px == tx - 1 && py == ty);
      while (ty > 0) {
        ope(px, py - 1), ope(px + 1, py), ope(px, py + 1), ope(px - 1, py),
            ope(px, py - 1);
      }
      tie(tx, ty) = pos[H - 1][0];
      while (tx < H - 2) {
        ope(px, py + 1), ope(px + 1, py), ope(px + 1, py), ope(px, py - 1),
            ope(px - 1, py);
      }
      ope(px + 1, py), ope(px + 1, py), ope(px, py + 1);
      ope(px - 1, py), ope(px, py - 1), ope(px - 1, py);
      ope(px, py + 1), ope(px + 1, py), ope(px + 1, py);
      ope(px, py - 1), ope(px - 1, py);
    }
    FOR(y, W) assert(A[H - 1][y] == (pair<int, int>{H - 1, y}));
    POP(A);
    solve_sort(A, ANS, tr);
  }
};

Back to top page