abc336F 旋转矩阵谜题

有一个大小为W*H的矩阵，每个格子里分别有1 ~ W*H的某个数字，对应1 ~ W*H的一个排列。每次可以选择大小为(W-1)*(H-1)的子矩阵旋转180度。给定初始状态，问20步以内是否可以将它还原？如果可以，输出最小步数，否则输出-1。
3<=H,W<=8; 1<=a[i][j]<=H*W; a[i][j]各不相等

bfs搜索，由于每一步都有4种情况，时间复杂度为O(4^{20)，会TLE，因此改用双向bfs，时间复杂度降为O(2*4}10)，可以通过。需要用哈希来判重。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)

using node = array<array<int,9>,9>;
const int m1 = 1000000123;
const int m2 = 1000000223;
void solve() {
    int H, W;
    cin >> H >> W;
    node s{}, t{};
    map<int,int> ms, mt;
    rep(i,1,H) rep(j,1,W) cin >> s[i][j];
    rep(i,1,H) rep(j,1,W) t[i][j] = (i-1)*W+j;

    auto rotate = [&](const node &u, node &v, int x, int y) {
        v = u;
        rep(i,1,H-1) rep(j,1,W-1) {
            v[i+x][j+y] = u[H-i+x][W-j+y];
        }
    };
    auto id = [&](const node &u) -> int {
        int h1 = 0, h2 = 0;
        rep(i,1,H) rep(j,1,W) {
            h1 = (h1 * 131 + u[i][j]) % m1;
            h2 = (h2 * 131 + u[i][j]) % m2;
        }
        return (h1<<32) + h2;
    };
    auto bfs = [&](node u, map<int,int> &mp) -> void {
        int step = 0;
        queue<node> q;
        q.push(u);
        while (!q.empty() && step <= 10) {
            int cnt = q.size();
            node x{}, y{};
            rep(i,1,cnt) {
                x = q.front(); q.pop();
                mp[id(x)] = step;
                rep(i,0,1) rep(j,0,1) {
                    rotate(x, y, i, j);
                    if (mp.count(id(y)) == 0) {
                        q.push(y);
                    }
                }
            }
            step += 1;
        }
    };

    bfs(s, ms);
    bfs(t, mt);
    int ans = 100;
    for (auto &[k,v] : mt) {
        auto it = ms.find(k);
        if (it != ms.end()) {
            ans = min(ans, v + it->second);
        }
    }
    if (ans == 100) {
        ans = -1;
    }
    cout << ans;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}