abc336F 旋转矩阵谜题

有一个H行W列的矩阵，记n=H*W，每个格子分别有个[1,n]内的数字，对应1~n的一个排列。每次可以选择大小为(H-1)*(W-1)的子矩阵旋转180度。
给定初始状态，问20步以内是否可以将它还原为1~n的排列？如果可以，输出最小步数，否则输出-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--)

const int b1 = 409, m1 = 1000000409;
const int b2 = 439, m2 = 1000000439;
const int b3 = 433, m3 = 1000000433;

using node = array<array<int,9>,9>;
using hval = tuple<int,int,int>;

void solve() {
    int H, W;
    cin >> H >> W;
    node s{}, t{};
    map<hval,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) -> hval {
        int h1 = 0, h2 = 0, h3 = 0;
        rep(i,1,H) rep(j,1,W) {
            h1 = (h1 * b1 + u[i][j]) % m1;
            h2 = (h2 * b2 + u[i][j]) % m2;
            h3 = (h3 * b3 + u[i][j]) % m3;
        }
        return {h1,h2,h3};
    };
    auto bfs = [&](node u, map<hval,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;
}