题解 P2578 【[ZJOI2005]九数码游戏】
encore
2019-07-18 17:52:58
思路和之前的大佬们差不多，主要在以下几个方面作了优化：
* 状态的表示
~~我也不知道有没有效果~~。观察两个操作，发现第二个操作只会移动3个元素，二第一个操作要移动8个。于是我按照以下方式定义我的状态：用一个9位十进制数表示，第一位（最高位）放九宫格中间的数，后面的8位异常为从九宫格左上角开始顺时针排列的数。
如以下棋盘：
| 0| 1| 2|
| -----------: | -----------: | -----------: |
| **3**| **4** | **5** |
| **6** | **7** | **8** |
对应状态数：
**401258763**
。
这样操作一就变得十分简单。残念的是，操作二变麻烦了。不过我~~盲目~~分析了一下，觉得总体上还是有优化的。
当然如果用16进制的话或许能减小常数，~~懒得弄了~~
* 状态的存储
在上文的基础上我使用了hashmap。主要是简单，相对康托展开应该要快一点。
~~由于比较简单就不提了~~
* 搜索的方式
这应该是我最有效的优化。在这里我使用了双端队列BFS。双端队列BFS就是从起点和终点分别扩展，使用两个队列，每次扩展节点数较少的那个。比较简单，具体不讲了，可以看后文的代码实现。这里只提一个需要注意的地方。就是从终点扩展的时候要用逆操作。具体来说，对于以下状态为**目标状态**
| 0| 1| 2|
| -----------: | -----------: | -----------: |
| **3**| **4** | **5** |
| **6** | **7** | **8** |
，
以下状态为**起始状态**
| 0| 1| 2|
| -----------: | -----------: | -----------: |
| **4**| **5** | **3** |
| **6** | **7** | **8** |
的情况。很明显，只要一步操作二即可完成。但是反向从终点开始扩展的话，就不能直接用原来的操作二。
~~语文不好真麻烦，还是看例子吧~~
就是说，操作二是把中间一行向右移，但如果反向扩展的话，往右移就会变成这样
| 0| 1| 2|
| -----------: | -----------: | -----------: |
| **5**| **3** | **4** |
| **6** | **7** | **8** |
这就不是起始状态了。
所以我们在从终点反向扩展的时候，要用一个操作的逆操作。比如操作二的逆操作就是把中间一行向左移。
还有就是路径输出的时候有一些区别。
好了，具体细节见代码：
```cpp
#include <cstdio>
#include <queue>
int ans;
inline void reada(int &x) {
while (x = getchar(), x > '9' || x < '0'); x -= 48;
}
class Hash{
public:
inline void assign(int Key, int val) {
int p = Key % _kMOD;
for (int e = first_[p]; e; e = next_[e]) {
if (val1_[e] == Key) { val2_[e] = val; return;}
}
next_[++edge_num_] = first_[p], first_[p] = edge_num_,
val1_[edge_num_] = Key, val2_[edge_num_] = val;
}
inline void modify(int Key, int val) {
int p = Key % _kMOD;
for (int e = first_[p]; e; e = next_[e]) {
if (val1_[e] == Key) { val2_[e] += val; return;}
}
next_[++edge_num_] = first_[p], first_[p] = edge_num_,
val1_[edge_num_] = Key, val2_[edge_num_] = val;
}
int query(int Key) const{
int p = Key % _kMOD;
for (int e = first_[p]; e; e = next_[e]) {
if (val1_[e] == Key) return val2_[e];
}
return 0;
}
protected:
static const int _kMOD = 999983;
static const int _kMaxSize = 363000;
private:
int edge_num_;
int first_[_kMOD], next_[_kMaxSize] , val1_[_kMaxSize], val2_[_kMaxSize];
};
int start_con;
int end_con = 401258763;
constexpr int pow10[10] = {1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000};
inline void conv(int &con, const int arr[]) {
con = arr[4] * pow10[8] + arr[0] * pow10[7] + arr[1] * pow10[6] +
arr[2] * pow10[5] + arr[5] * pow10[4] + arr[8] * pow10[3] +
arr[7] * pow10[2] + arr[6] * pow10[1] + arr[3] * pow10[0];
}
inline void iconv(int con, int arr[]) {
arr[3] = con % 10, con /= 10,
arr[6] = con % 10, con /= 10,
arr[7] = con % 10, con /= 10,
arr[8] = con % 10, con /= 10,
arr[5] = con % 10, con /= 10,
arr[2] = con % 10, con /= 10,
arr[1] = con % 10, con /= 10,
arr[0] = con % 10, con /= 10,
arr[4] = con % 10;
}
void out_put_con(int con) {
int x[9];
iconv(con, x);
putchar(x[0] + '0'),
putchar(' '),
putchar(x[1] + '0'),
putchar(' '),
putchar(x[2] + '0'),
putchar('\n'),
putchar(x[3] + '0'),
putchar(' '),
putchar(x[4] + '0'),
putchar(' '),
putchar(x[5] + '0'),
putchar('\n'),
putchar(x[6] + '0'),
putchar(' '),
putchar(x[7] + '0'),
putchar(' '),
putchar(x[8] + '0'),
putchar('\n');
}
Hash dis1, dis2, pre1, pre2, vis;
int mid;
void operator_A(int &con) {
int h = con / pow10[8], t = con % pow10[8];
con = h * pow10[8] + (t % 10) * pow10[7] + t / 10;
}
void operator_B(int &con) {
int s1, s2, s3, s4, s5;
s5 = con % 10,
con /= 10,
s4 = con % pow10[3],
con /= pow10[3],
s3 = con % 10,
con /= 10,
s2 = con % pow10[3],
con /= pow10[3],
s1 = con;
con = s3 + s4 * 10 + s1 * pow10[4] +
s2 * pow10[5] + s5 * pow10[8];
}
void inv_operator_A(int &con) {
int h = con / pow10[8], t = con % pow10[8];
con = h * pow10[8] + (t / pow10[7]) + (t % pow10[7]) * 10;
}
void inv_operator_B(int &con) {
int s1, s2, s3, s4, s5;
s5 = con % 10,
con /= 10,
s4 = con % pow10[3],
con /= pow10[3],
s3 = con % 10,
con /= 10,
s2 = con % pow10[3],
con /= pow10[3],
s1 = con;
con = s1 + s4 * 10 + s5 * pow10[4] +
s2 * pow10[5] + s3 * pow10[8];
}
void (*FPArray[])(int&) = {operator_A, operator_B, inv_operator_A, inv_operator_B};
int BFS(int start_con, int end_con) {
std::queue<int> q1, q2, *q;
Hash *dis, *pre;
int qv, fpa;
bool flag = false;
q1.emplace(start_con), q2.emplace(end_con);
vis.assign(start_con, 1), vis.assign(end_con, 2);
dis1.assign(start_con, 0), dis2.assign(end_con, 0);
while ((!q1.empty()) && (!q2.empty())) {
if (q1.size() <= q2.size()) {
q = &q1, dis = &dis1, pre = &pre1, qv = 1, fpa = 0;
} else {
q = &q2, dis = &dis2, pre = &pre2, qv = 2, fpa = 2;
}
int qf = q->front(), dist = dis->query(qf);
q->pop();
for (int i = 0, qtf; i != 2; ++i) {
qtf = qf;
(i + fpa)[FPArray](qtf);
int v = vis.query(qtf);
if (v == qv) continue;
vis.modify(qtf, qv);
dis->assign(qtf, dist + 1);
pre->assign(qtf, qf);
if (v + qv == 3) {
mid = qtf;
flag = true;
break;
}
q->emplace(qtf);
}
if (flag) break;
}
if (flag) {
return dis1.query(mid) + dis2.query(mid);
}
return -1;
}
void print_path_A(int x) {
if (!x) return;
print_path_A(pre1.query(x));
out_put_con(x), putchar('\n');
}
void print_path_B(int x) {
while (x) {
out_put_con(x), putchar('\n');
x = pre2.query(x);
}
}
void print_path(int mid) {
print_path_A(pre1.query(mid)), print_path_B(mid);
}
int main() {
int x[9];
reada(x[0]),
reada(x[1]),
reada(x[2]),
reada(x[3]),
reada(x[4]),
reada(x[5]),
reada(x[6]),
reada(x[7]),
reada(x[8]);
conv(start_con, x);
ans = BFS(start_con, end_con);
if (ans == -1) { puts("UNSOLVABLE");}
else {
printf("%d\n", ans);
print_path(mid);
}
return 0;
}
```
注释：
为了$\overset{\text{毒瘤}}{\text{方便}}$，我使用了指针。~~而且是函数指针~~。在```void (*FPArray[])(int&)``` 那里定义了一个名为FPArray的函数指针数组。```i[FParray](con)```表示调用FPArray中第i个函数，参数为con。
conv函数用于将状态数值转换成状态数组，iconv则相反。
hashmap vis里1为正面扩展过，2为反向扩展过，3为相遇。
出锅了或者有问题评论或者@我吧。
交了一下，173ms，没吸氧~~吸了也没用~~，目前排第五。不会卡常。$\overset{\text{不会}}{\text{不想}}$优化了。如果要冲榜我建议手写队列、循环展开、改哈希模数、输出优化之类。
顺便%%12ms的大佬，不知道用的什么神仙算法Orz
祝你们成功（滑稽