SRM 618 div2 900

一个nXn棋盘, 每行有一个棋子, 若任意每对棋子不同行同列该棋盘为和平棋盘

现给出两个和平棋盘, 问是否能经过K步操作将棋盘1转化为棋盘2

1<=n<=8, K未知

观察

..:

一道非常裸的搜索题, 外加一点一点记忆化的思想, 细节见代码
记忆话检查的办法收到了SRM628某题的启发, 使用了8进制表示法

写出代码

..:

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vin;
typedef map<int, int> mii;

int n, f;
mii v;
vin g, t;
inline void dodo() {
    int k=0, i;
    for (i=0; i<n; i++) k+=g[i]*pow(8, i);
    if (v[k])
        return;
    v[k]=1;
    for (i=0; i<n; i++) if (g[i]!=t[i])
        break;
    if (i==n) {
        f=1;
        return;
    }
    int t;
    for (int i=1; !f && i<n; i++)
        for (int j=0; !f && j<i; j++) if (g[j]>g[i]) {
            t=g[i], g[i]=g[j], g[j]=t;
            dodo();
            t=g[i], g[i]=g[j], g[j]=t;
        }
}
class MovingRooksDiv2 {
public:
 string move(vector <int> Y1, vector <int> Y2) {
        n=Y1.size();
        g=Y1;
        t=Y2;
        dodo();
        return f ? "Possible" :
                   "Impossible";
    }
};