题目跳转
HDOJ3567
题目大意
经典八数码问题，和POJ1077相比，指定了末位置，并且要求输出最小字典序。
思路
DBFS - 康托展开 - 状态压缩
- DBFS
- 考虑到确定了起点和终点，并且可以互相到达，采用
双向广搜。
- 考虑到确定了起点和终点，并且可以互相到达，采用
- 康托展开
- 对八数码状态的绝配Hash
- 状态压缩
- 采用四进制来存储路径，经暴力可得，步数最大30左右。
我的原始思路TLE：
代码语言：javascript复制map做`状态`和`路径`的映射，同时充当标记的作用。
代码会贴在文末其他说明
并不是正搜，只按字典序小，倒搜只按字典序大就对，需要再把状态搜完比较！
该处有一个数据生成器
只是缺少了始末状态一致的数据，导致我血压高了几小时。（和标程对拍没有问题，交上去就WA）
CODE
代码语言：javascript复制#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
struct Node
{
char str[12];
int pos, hx, step; // X的位置，哈希值，步数
LL path; // 0123 - dlru
int is_ordered; //是否有序
};
// 预处理阶乘
const int factory[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int ans_step;
LL ans; // 路径的数字形式
LL power4[40]; // 35
char ans_path[40], dir[5] = "dlru";
int d[2][362890]; // dist 1代表正序，0代表倒叙，下同
LL road[2][362890]; // 存储字典序最小的路径
queue<Node> q;
void prev_calc() // 预处理4的n次方
{
LL t = 1; // LL!
for (int i = 0; i < 35; i , t *= 4)
power4[i] = t;
}
void init() // 初始化
{
while (q.size())
q.pop();
memset(d, -1, sizeof d);
memset(road, 0, sizeof road);
ans_step = ans = -1;
return;
}
int cantor(char ch[], int n = 9) // 康托展开
{
int Idx = 0, cnt;
for (int i = 0; i < n; i )
{
cnt = 0;
for (int j = i 1; j < n; j )
if (ch[i] > ch[j])
cnt ;
Idx = cnt * factory[n - i - 1];
}
return Idx;
}
// 其实必要性不大的函数
Node mk_Node(char ch[], int pos, int step, LL path, int is_ordered)
{
if (pos == -1)
{
for (int i = 0; i < 9; i )
if (ch[i] == 'X')
{
pos = i;
break;
}
}
Node t = (Node){{}, pos, cantor(ch), step, path, is_ordered};
memcpy(t.str, ch, 9);
return t;
}
void check_nstatus(Node t, Node &nt, int type)
{
if (d[nt.is_ordered][nt.hx] == -1) // 未访问过
{
d[nt.is_ordered][nt.hx] = t.step 1; // 更新最小步数
if (nt.is_ordered) // 生成新路径
nt.path = nt.path * 4 type;
else
nt.path = (3 - type) * power4[nt.step - 1] nt.path;
road[nt.is_ordered][nt.hx] = nt.path;
// 剪枝 - 因为第一次相遇就是最小步数，尽可能让他们的步数相近
if (ans == -1 || nt.step * 2 <= ans_step)
q.push(nt);
}
else // 访问过 - 更新字典序
{
if (t.step 1 > d[nt.is_ordered][nt.hx]) // 步数比之前到达过的大
return;
else
d[nt.is_ordered][nt.hx] = t.step 1; // 更新最小步数
if (nt.is_ordered) // 生成新路径
nt.path = nt.path * 4 type;
else
nt.path = (3 - type) * power4[nt.step - 1] nt.path;
if (road[nt.is_ordered][nt.hx] > nt.path) // 字典序小
{
road[nt.is_ordered][nt.hx] = nt.path;
// 剪枝 - 因为第一次相遇就是最小步数，尽可能让他们的步数相近
if (ans == -1 || nt.step * 2 <= ans_step)
q.push(nt);
}
}
// 相遇
if (d[nt.is_ordered ^ 1][nt.hx] != -1 && (ans == -1 || ans_step == nt.step d[nt.is_ordered ^ 1][nt.hx]))
{
ans_step = nt.step d[nt.is_ordered ^ 1][nt.hx];
LL tans; // 临时变量
if (nt.is_ordered)
tans = nt.path * power4[d[0][nt.hx]] road[0][nt.hx];
else
tans = road[1][nt.hx] * power4[d[0][nt.hx]] nt.path;
if (ans == -1 || tans < ans)
ans = tans;
}
}
void update_nstatus(Node t, int type) // 生成新状态
{
// dlru
Node nt = t;
switch (type)
{
case 0:
if (nt.pos < 6)
{
swap(nt.str[nt.pos], nt.str[nt.pos 3]);
nt.pos = 3;
nt.step ;
nt.hx = cantor(nt.str);
check_nstatus(t, nt, type);
}
break;
case 1:
if (nt.pos % 3)
{
swap(nt.str[nt.pos], nt.str[nt.pos - 1]);
nt.pos--;
nt.step ;
nt.hx = cantor(nt.str);
check_nstatus(t, nt, type);
}
break;
case 2:
if (nt.pos % 3 != 2)
{
swap(nt.str[nt.pos], nt.str[nt.pos 1]);
nt.pos ;
nt.step ;
nt.hx = cantor(nt.str);
check_nstatus(t, nt, type);
}
break;
case 3:
if (nt.pos >= 3)
{
swap(nt.str[nt.pos], nt.str[nt.pos - 3]);
nt.pos -= 3;
nt.step ;
nt.hx = cantor(nt.str);
check_nstatus(t, nt, type);
}
break;
}
}
void dbfs(char A[], char Z[])
{
Node a = mk_Node(A, -1, 0, 0, 1), b = mk_Node(Z, -1, 0, 0, 0);
q.push(a), q.push(b);
d[1][a.hx] = d[0][b.hx] = 0;
road[1][a.hx] = road[0][b.hx] = 0;
if (a.hx == b.hx)
{
ans_step = 0;
ans = 0;
return;
}
while (q.size())
{
Node t = q.front();
q.pop();
for (int i = 0; i < 4; i )
update_nstatus(t, i);
}
}
void trans_path()
{
for (int i = ans_step - 1; i >= 0; i--)
ans_path[ans_step - 1 - i] = dir[(ans / power4[i]) % 4LL];
ans_path[ans_step] = ' '; // 重置，不然会使得上次对char*的更改对下次输出有影响。
}
main()
{
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
prev_calc();
int T;
scanf("%d", &T);
for (int C = 1; C <= T; C )
{
init();
char A[12], Z[12];
scanf("%sn%s", A, Z);
dbfs(A, Z);
trans_path(); // 数字路径转化为字符路径
printf("Case %d: %dn%sn", C, ans_step, ans_path);
}
return 0;
}map朴素写法 - TLE
代码语言：javascript复制#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <unordered_map>
using namespace std;
string ans;
char ch[5] = "dlru";
queue<string> q[2];
unordered_map<string, string> mp[2];
void init()
{
for (int i = 0; i < 2; i )
{
mp[i].clear();
while (q[i].size())
q[i].pop();
}
ans = "n";
}
string get_nstatus(string str, int pos, int type)
{
switch (type)
{
// down
case 0:
if (pos < 6)
swap(str[pos], str[pos 3]);
else
str = "n";
break;
// left
case 1:
if (pos % 3 != 0)
swap(str[pos], str[pos - 1]);
else
str = "n";
break;
// right
case 2:
if (pos % 3 != 2)
swap(str[pos], str[pos 1]);
else
str = "n";
break;
// up
case 3:
if (pos >= 3)
swap(str[pos], str[pos - 3]);
else
str = "n";
break;
}
return str;
}
void update_nstatus(queue<string> &q, unordered_map<string, string> &mp1, unordered_map<string, string> &mp2, string t, int pos, int i, bool is_ordered)
{
string nt = get_nstatus(t, pos, i);
if (nt != "n" && (!mp1.count(nt) || mp1[t].size() 1 <= mp1[nt].size())) // 是小于等于啊，等于可以带来字典序的优化！！！！
{
if (is_ordered && (!mp1.count(nt) || mp1[t] ch[i] < mp1[nt])) // 要判断没有 或者 字典序更小
{
mp1[nt] = mp1[t] ch[i];
if (mp2.count(nt))
{
string res = mp1[nt] mp2[nt];
if (ans == "n" || (res.size() == ans.size() && res < ans))
ans = res;
}
}
else if (!is_ordered && (!mp1.count(nt) || ch[3 - i] mp1[t] < mp1[nt]))
{
mp1[nt] = ch[3 - i] mp1[t];
if (mp2.count(nt))
{
string res = mp2[nt] mp1[nt];
if (ans == "n" || (res.size() == ans.size() && res < ans))
ans = res;
}
}
if (ans != "n" && mp1[nt].size() * 2 > ans.size())
return;
q.push(nt);
}
}
void expand(queue<string> &q, unordered_map<string, string> &mp1, unordered_map<string, string> &mp2, bool is_ordered)
{
string t = q.front();
q.pop();
int pos;
for (int i = 0; i < 9; i )
if (t[i] == 'X')
{
pos = i;
break;
}
// dlru
for (int i = 3; i >= 0; i--)
update_nstatus(q, mp1, mp2, t, pos, i, is_ordered);
}
void dbfs(string A, string Z)
{
mp[0][A] = "", mp[1][Z] = "";
q[0].push(A), q[1].push(Z);
while (q[0].size() && q[1].size())
{
if (q[0].size() < q[1].size())
expand(q[0], mp[0], mp[1], true);
else
expand(q[1], mp[1], mp[0], false);
}
// for(auto x: mp[0])
// cout << x.second.size() << endl;
for (int i = 0; i < 2; i )
{
while (q[i].size())
expand(q[i], mp[i], mp[1 - i], !i);
}
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
scanf("%d", &T);
for (int Case0 = 1; Case0 <= T; Case0 )
{
init();
string A, Z;
cin >> A >> Z;
dbfs(A, Z);
printf("Case %d: %dn", Case0, ans.size());
cout << ans << 'n';
}
return 0;
}
