一、思路很简单，搜索。对于每一种状态，利用康托展开编码成一个整数。于是，状态就可以记忆了。
二、在搜索之前，可以先做个优化，对于逆序数为奇数的序列，一定无解。
三、搜索方法有很多。
1、最普通的：深搜、广搜。在这题里面，这两个方法直接TLE。所以，我后面没有贴超时的代码。
2、既然1超时，那就预处理出所有状态，用map存储，然而，map的insert（使用[]是一样的）实在太慢了，也超时。
3、在1的基础上，优化一下，得到：IDA*，双向广搜，A*。
3、IDA*我没尝试，不过感觉没有A*快。另外，双向广搜可以加优化，在HDU上可以快大概300ms，就是：对于某一个方向，在开始BFS时，如果当前的队列里面状态个数很多，而另外一个队列里面相对较少，那么，把搜索方面换成另一边。这样，不至于出现两个队列的状态个数相差太远以至于退化成单向BFS的情况。当然，这个题两个队列中的状态都是比较均匀的，即使不加优化，效果也不会太差。
4、不管用的是什么搜索，搜索过程中，多个样例经历经历相同的状态是非常有可能的，所以，理论上来说，可以加缓存，也就是其实不管是什么样例，只要序列确定，得到的整数编码一定是确定的，所以，理论上来说，加缓存可以加速，然而， 不知为何，这题，加了缓存还更慢。多半是因为我的缓存用的是C++ STL吧。
四、注意点
1、双向BFS加优化时，C++的queue的size()的返回值类型是unsigned int，直接相减，会发生溢出的情况， 导致size()小的队列大小一直不变，size()大的队列一直在扩大，也就是退化成了单向BFS了。T_T。所以，为了防止这种情况发生，在size相减之前，用两个int变量先存储好这两个队列的size。否则，会很坑。
2、在循环中开辟新指针，每一次循环开辟的指针值都一样，如代码所示。
#include<bits/stdc++.h>
using namespace std;
typedef struct Foo{
int v1, v2;
Foo(int _v1,int _v2){
v1 = _v1;
v2 = _v2;
}
Foo(){}
}Node;
set<Node*> s;
int main(){
;i < ;++i){
Node node = Node(i, i);
s.insert(&node);
}
printf("%d\n", s.size());
}
输出结果会是1，而不是5。特别要注意。而如果这么写：
#include<bits/stdc++.h>
using namespace std;
typedef struct Foo{
int v1, v2;
Foo(int _v1,int _v2){
v1 = _v1;
v2 = _v2;
}
Foo(){}
}Node;
set<Node*> s;
int main(){
;i < ;++i){
Node* pnode = new Node(i, i);
s.insert(pnode);
}
printf("%d\n", s.size());
}
因为C++没有自动垃圾回收，所以，很有可能会出现MLE的情况。因此，ACM竞赛中，尽可能地不要使用指针。
3、C++的容器，map、string、vector之类的，慢！慢！慢！如果条件允许，时间又压得比较紧，特别是像string这种的，最好还是用C语言原生的字符串数组，虽然麻烦些，但是比string快不只一点点。
五、源代码
1、双向BFS（队列容量均衡优化）
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
];
void init() {
facts[] = facts[] = ;
; i <= ; ++i)facts[i] = facts[i - ] * i;
}
int encode(vector<int>& seq) {
;
int num = seq.size();
; i < num - ; ++i) {
;
; j < i; ++j) {
if(seq[j] < seq[i])--cnt;
}
res += cnt * facts[num - i - ];
}
return res;
}
vector<int> temp;
void decode(int n, int m) {
temp.clear();
;
int i, j, r, t;
; --t) {
r = m / facts[t - ];
m %= facts[t - ];
; i <= n; ++i) {
)) {
)break;
--r;
}
}
temp.push_back(i);
buf |= << i;
}
}
];
int get() {
vector<int> vec;
int len = strlen(line);
; i < len; ++i) {
');
);
}
;
, sz = vec.size(); i < sz; ++i) {
)continue;
; j < i; ++j) {
)continue;
if(vec[j] > vec[i])++cnt;
}
}
);
else return encode(vec);
}
int findPos() {
; i < ; ++i))return i;
;
}
typedef struct Foo {
int code;
char step;
Foo(int l, char s) {
code = l;
step = s;
}
Foo() {}
} Node;
];
, , -, };
queue<];
][];
Node pre[][];
bool bfs(int s[]) {
; i < ; ++i) {
res[i].clear();
while(!que[i].empty())que[i].pop();
memset(vis[i], , sizeof(vis[i]));
vis[i][s[i]] = true;
; j < ; ++j)pre[i][j].code = -;
que[i].push(s[i]);
}
;
while(!que[k].empty()) {
].size();
)k ^= ;//队列均衡优化
int code = que[k].front();
que[k].pop();
][code]) {
; i < ; ++i) {
int now = code;
int last = pre[i][now].code;
) {
res[i].push_back(pre[i][now].step);
now = last;
last = pre[i][last].code;
}
)reverse(res[i].begin(), res[i].end());
}
return true;
}
decode(, code);
int pos = findPos();
; i < ; ++i) {
int np = pos + dirs[i];
|| np > )continue;
bool cond = false;
|| i == )cond = (np / == pos / );
|| i == )cond = (np >= && np <= );
if(cond) {
swap(temp[np], temp[pos]);
int nv = encode(temp);
if(!vis[k][nv]) {
)pre[k][nv] = Node(code, 'l');
)pre[k][nv] = Node(code, 'r');
)pre[k][nv] = Node(code, 'u');
)pre[k][nv] = Node(code, 'd');
que[k].push(nv);
vis[k][nv] = true;
}
swap(temp[np], temp[pos]);
}
}
k ^= ;
}
return false;
}
void change(string& s) {
, len = s.length(); i < len; ++i) {
if(s[i] == 'l')s[i] = 'r';
else if(s[i] == 'r')s[i] = 'l';
else if(s[i] == 'u')s[i] = 'd';
else if(s[i] == 'd')s[i] = 'u';
}
reverse(s.begin(), s.end());
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
ios::sync_with_stdio(false);
init();
while(gets(line) != NULL) {
int v = get();
)cout << "unsolvable" << endl;
)cout << endl;
else {
};
if(bfs(s)) {
change(res[]);
cout << res[] << res[] << endl;
} else cout << "unsolvable" << endl;
}
}
}
2、A*搜索。
#include<bits/stdc++.h>
using namespace std;
];
];
typedef struct Foo {
int code;
int pos9;
double g, h;
Foo(int c, int p, double _g, double _h) {
code = c;
pos9 = p;
g = _g;
h = _h;
}
Foo() {}
/*这里写法决定时间的数量级：
用注释的这种写法：耗时2700+ms；
用没注释的这种写法，if括号里写成fabs(h - ano.h) < 1e-8,耗时1200+ms；
现在这种写法：耗时800+ms;；
*/
bool operator < (const Foo ano) const {
// if(fabs(f - ano.f) < 1e-8)return h > ano.h;
// else return f > ano.f;
if(h == ano.h)return g > ano.g;
else return h > ano.h;
}
} Node;
void init0() {
facts[] = facts[] = ;
; i < ; ++i)facts[i] = facts[i - ] * i;
}
int encode(string& seq) {
, len = seq.length(), i, j, cnt;
; i < len; ++i) {
cnt = (seq[i] - ');
; j < i; ++j)if(seq[j] < seq[i])--cnt;
res += cnt * facts[len - i - ];
}
return res;
}
string decode(int code) {
;
string res;
; t > ; --t) {
r = code / facts[t - ];
code %= facts[t - ];
; i <= ; ++i) {
)) {
)break;
else --r;
}
}
res.push_back(i + ');
board |= << i;
}
return res;
}
double distance(int src) {
double res = 0.0;
string seq = decode(src);
int len = seq.length();
int i, j, x0, y0, x1, y1, num;
; i < len; ++i) {
num = seq[i] - ';
x0 = (num - ) / , y0 = (num - ) % ;
x1 = i / , y1 = i % ;
res += abs(x0 - x1) + abs(y0 - y1);
}
return res;
}
int find_pos9(string& str) {
int len = str.length(), i;
; i < len; ++i)')return i;
;
}
, , -, };
priority_queue<Node> que;
];
pair<];
string ans;
bool bfs(int s) {
int i, j, k;
int pos9, npos9, ncode;
string seq;
Node top_node;
while(!que.empty())que.pop();
memset(vis, , sizeof(vis));
; i < facts[]; ++i)pre[i].first = -;
vis[s] = true;
seq = decode(s);
pos9 = find_pos9(seq);
que.push(Node(s, pos9, , distance(s)));
while(!que.empty()) {
top_node = que.top();
que.pop();
) {
ans.clear();
; now = last, last = pre[last].first) {
ans.push_back(pre[now].second);
}
reverse(ans.begin(), ans.end());
return true;
}
seq = decode(top_node.code);
pos9 = top_node.pos9;
; i < ; ++i) {
npos9 = pos9 + dirs[i];
|| npos9 > )continue;
|| i == ) && npos9 / != pos9 / )continue;
|| i == ) && (npos9 < || npos9 > ))continue;
swap(seq[npos9], seq[pos9]);
ncode = encode(seq);
if(!vis[ncode]) {
pre[ncode].first = top_node.code;
)pre[ncode].second = 'l';
)pre[ncode].second = 'r';
)pre[ncode].second = 'u';
)pre[ncode].second = 'd';
que.push(Node(ncode, npos9, top_node.g + , distance(ncode)));
vis[ncode] = true;
}
swap(seq[npos9], seq[pos9]);
}
}
return false;
}
int get_code(char str[]) {
string temp;
int len = strlen(str), i, j, cnt;
; i < len; ++i) {
if(isdigit(str[i]))temp.push_back(str[i]);
');
}
cnt = ;
len = temp.length();
; i < len; ++i) {
')continue;
; j < i; ++j) {
')continue;
if(temp[j] > temp[i])++cnt;
}
}
);
else return encode(temp);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
ios::sync_with_stdio(false);
init0();
while(gets(input) != NULL) {
int code = get_code(input);
)cout << "unsolvable" << endl;
)cout << endl;
else cout << (bfs(code) ? ans : "unsolvable") << endl;
}
;
}
3、纯C语言版A*算法。耗时：400+ms。其实priority_queue和stack等都是C++ STL。^_^
#include<bits/stdc++.h>
using namespace std;
];
];
typedef struct Foo {
];
int code, pos9;
double g, h;
Foo(char s[], int c, int p, double _g, double _h) {
strcpy(seq, s);
code = c, pos9 = p;
g = _g, h = _h;
}
Foo() {}
bool operator < (const Foo ano) const {
if(h == ano.h)return g > ano.g;
else return h > ano.h;
}
} Node;
void init0() {
facts[] = facts[] = ;
; i < ; ++i)facts[i] = facts[i - ] * i;
}
int encode(const char seq[]) {
, i, j, cnt, len = strlen(seq);
; i < len; ++i) {
cnt = seq[i] - ';
; j < i; ++j)if(seq[j] < seq[i])--cnt;
res += cnt * facts[len - i - ];
}
return res;
}
int find_pos9(const char str[]) {
int len = strlen(str), i;
; i < len; ++i)')return i;
;
}
double dist(const char str[]) {
int len = strlen(str), i, x0, y0, x1, y1, num;
double res = 0.0;
; i < len; ++i) {
num = str[i] - ';
x0 = (num - ) / , y0 = (num - ) % ;
x1 = i / , y1 = i % ;
res += abs(x0 - x1) + abs(y0 - y1);
}
return res;
}
, , -, };
priority_queue<Node> que;
];
pair<];
stack<char> ans;
bool bfs(int s) {
int i, j, k;
Node node, new_node;
while(!que.empty())que.pop();
memset(vis, , sizeof(vis));
; i < facts[]; ++i)pre[i].first = -;
vis[s] = true;
que.push(Node(input, s, find_pos9(input), , dist(input)));
while(!que.empty()) {
node = que.top();
que.pop();
) {
while(!ans.empty())ans.pop();
].first, now = ; last != -; now = last, last = pre[last].first)
ans.push(pre[now].second);
return true;
}
; i < ; ++i) {
new_node = node;
new_node.pos9 += dirs[i];
|| new_node.pos9 > )continue;
|| i == ) && (new_node.pos9 / != node.pos9 / ))continue;
swap(new_node.seq[new_node.pos9], new_node.seq[node.pos9]);
new_node.code = encode(new_node.seq);
if(!vis[new_node.code]) {
++new_node.g;
new_node.h = dist(new_node.seq);
que.push(new_node);
vis[new_node.code] = true;
pre[new_node.code].first = node.code;
)pre[new_node.code].second = 'l';
)pre[new_node.code].second = 'r';
)pre[new_node.code].second = 'u';
)pre[new_node.code].second = 'd';
}
}
}
return false;
}
int get_code(char str[]) {
];
int i, j, len = strlen(str);
, j = ; i < len; ++i) {
if(isdigit(str[i]))temp[j++] = str[i];
';
}
temp[j++] = '\0';
memset(input, '\0', sizeof(input));
strcpy(input, temp);
;
len = j - ;
; i < len; ++i) {
')continue;
; j < i; ++j) {
')continue;
if(temp[j] < temp[i])++cnt;
}
}
);
else return encode(temp);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
init0();
while(gets(input) != NULL) {
int code = get_code(input);
)printf("unsolvable\n");
)putchar('\n');
else {
if(bfs(code)) {
for(; !ans.empty(); ans.pop())putchar(ans.top());
putchar('\n');
} else printf("unsolvable\n");
}
}
;
}
六、A*算法确实是厉害。估值函数写得好可以很快；写不好，效果就会很差，甚至退化成普通的BFS。