【算法竞赛 - 搜索】八数码
题目跳转
题目大意
经典八数码问题，无需赘述。
本人思路
BFS - 康托展开 - A*
- 上下左右移动的操作直接自己想好二维的形态，直接在一维中实现
- 将每个
没有在自己位置的棋子与自己的应在的位置的曼哈顿距离之和作为估价函数f - 康托展开进行哈希
我的其他思路：
- 用
map代替康托展开来哈希- 不加A* TLE
- 加了A* 比康托展开慢
- 康托展开的复杂度为O(n^2)，而map的时间复杂度为O(nlogn)，但是不难发现，用map实现时，会多次调用map中时间复杂度为O(logn)的函数，导致常数较大，而
本题n很小，所以导致map比康托展开慢 - 代码会附在正解后面
- 本题只用康托展开也会TLE，但代码不再展示。
CODE
/*************************\
*不加逆序对特判无解 2552 ms*
* 加了 76 ms *
\*************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int N = 362880;
const int factory[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
struct Node
{
int val;
string st, path;
bool operator<(const Node &o) const
{
return val > o.val;
}
};
bool vis[N];
string str;
priority_queue<Node> heap;
bool Cantor(string str, int n = 9)
{
int CantorIdx = 0;
for (int i = 0; i < n; i++)
{
int cnt = 0;
for (int j = i + 1; j < n; j++)
if (str[i] > str[j])
cnt++;
CantorIdx += cnt * factory[n - i - 1];
}
if (!vis[CantorIdx])
{
vis[CantorIdx] = true;
return false;
}
return true;
}
int f(string str, int n = 9)
{
int res = 0;
for (int i = 0; i < n; i++)
if (str[i] != 'x')
{
int t = str[i] - '1';
int oa = t / 3, ob = t % 3;
int na = i / 3, nb = i % 3;
res += abs(oa - na) + abs(ob - nb);
}
return res;
}
void bfs()
{
heap.push((Node){f(str), str, ""});
Cantor(str);
while (heap.size())
{
Node t = heap.top(), tmp;
heap.pop();
// cout << t.val << " " << t.st << " " << t.path << endl;
if (t.st == "12345678x")
{
cout << t.path << '\n';
return;
}
int pos;
for (int i = 0; i < 9; i++)
if (t.st[i] == 'x')
pos = i;
tmp = t;
if (pos >= 3) // up
{
swap(tmp.st[pos], tmp.st[pos - 3]);
if (!Cantor(tmp.st))
{
tmp.path += 'u';
tmp.val = f(tmp.st) + tmp.path.size();
heap.push(tmp);
}
}
tmp = t;
if (pos < 6) // down
{
swap(tmp.st[pos], tmp.st[pos + 3]);
if (!Cantor(tmp.st))
{
tmp.path += 'd';
tmp.val = f(tmp.st) + tmp.path.size();
heap.push(tmp);
}
}
tmp = t;
if (pos % 3 != 0) // left
{
swap(tmp.st[pos], tmp.st[pos - 1]);
if (!Cantor(tmp.st))
{
tmp.path += 'l';
tmp.val = f(tmp.st) + tmp.path.size();
heap.push(tmp);
}
}
tmp = t;
if (pos % 3 != 2) // right
{
swap(tmp.st[pos], tmp.st[pos + 1]);
if (!Cantor(tmp.st))
{
tmp.path += 'r';
tmp.val = f(tmp.st) + tmp.path.size();
heap.push(tmp);
}
}
}
cout << "unsolvable" << '\n';
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
for (int i = 0; i < 9; i++)
{
char ch;
cin >> ch;
str += ch;
}
// spj 无解
int cnt = 0;
for (int i = 0; i < str.size(); i++)
for (int j = i + 1; j < str.size(); j++)
if (str[i] > str[j] && str[i] != 'x' && str[j] != 'x')
cnt++;
if (cnt & 1)
cout << "unsolvable" << '\n';
else
bfs();
return 0;
}只用map实现 - TLE
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
struct Node
{
string st, path;
};
string str;
queue<Node> q;
map<string, int> strInt;
void bfs()
{
q.push((Node){str, ""});
strInt[str] = 0;
while (q.size())
{
Node t = q.front(), tmp;
q.pop();
if (t.st == "12345678x")
{
cout << t.path << '\n';
return;
}
int pos;
for (int i = 0; i < 9; i++)
if (t.st[i] == 'x')
pos = i;
tmp = t;
if (pos >= 3) // up
{
swap(tmp.st[pos], tmp.st[pos - 3]);
if (strInt.count(tmp.st) == 0)
{
tmp.path += 'u';
strInt[tmp.st] = strInt[t.st] + 1;
q.push(tmp);
}
}
tmp = t;
if (pos < 6) // down
{
swap(tmp.st[pos], tmp.st[pos + 3]);
if (strInt.count(tmp.st) == 0)
{
tmp.path += 'd';
strInt[tmp.st] = strInt[t.st] + 1;
q.push(tmp);
}
}
tmp = t;
if (pos % 3 != 0) // left
{
swap(tmp.st[pos], tmp.st[pos - 1]);
if (strInt.count(tmp.st) == 0)
{
tmp.path += 'l';
strInt[tmp.st] = strInt[t.st] + 1;
q.push(tmp);
}
}
tmp = t;
if (pos % 3 != 2) // right
{
swap(tmp.st[pos], tmp.st[pos + 1]);
if (strInt.count(tmp.st) == 0)
{
tmp.path += 'r';
strInt[tmp.st] = strInt[t.st] + 1;
q.push(tmp);
}
}
}
cout << "unsolvable" << '\n';
return;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
for (int i = 0; i < 9; i++)
{
char ch;
cin >> ch;
str += ch;
}
bfs();
return 0;
}
// map TLE 怀疑是常数比较大
// unordered_map POJ不支持，acwing是过了，且先上下快点本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022年08月12日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
