一、题意
这是一个八数码问题的变种。
输入九宫格的初始状态，九宫格的数字为0...8，其中0代表为空位，其余数字代表由相应数字的板块在那个位置上。
然后对九宫格里的板块进行移动，直到变成一个最终状态。
要求输出变成的最远的状态，即操作次数最多的状态。
打印出这个最终状态，同时用“UDLR”输出空位的移动路径。
二、解析
最短路径可以用bfs，最长路径当然也可以用bfs。
只不过这道题目的状态点比较大，需要记录所有9个数字。
这样就有个问题，vis数组应该如何处理？我们不可能开一个9维的数组，也开不起10^9的数组。
这里有三种方案：
- 为这9个数字的数组进行简单编码，然后vis用一个set<int> 进行判定。
这种方法可以作为一个“跳板”方法，来确保主算法正确，然后再修改为下面两种方法之一（当然如果没超时也可以用）。</int> - 哈希法。为这9个数字的数组进行编码后，放到哈希表中进行维护。这里的哈希表需要解决冲突问题，因此实际上是用一个list<> vis[maxn]实现。然后实现相应的insert、query、clear操作即可。
- 康托法。也即是康托展开，它是一种可以完美实现数组和编码相互转换的方法，实际上就是吧数组在全排列中排第几个作为编码值。好处是效率高，不好就是代码量大。
所以还是推荐用哈希法。
三、代码
- 哈希法的实现
#include <iostream>
#include <queue>
#include <string>
#include <list>
using namespace std;
const int Fx[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const string Ord = "ULDR";
const int HASH = 100003;
class node {
public:
int val[3][3];
int x, y;
string path;
node() {}
int getCode() const {
int res = 0;
for(int i = 0; i < 3; i ++) for(int j = 0; j < 3; j ++) res = res * 10 + val[i][j];
return res;
}
void output() {
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j ++) cout << (j ? " " : "") << val[i][j];
cout << "\n";
}
}
};
int kase;
node u0;
// 哈希表写法
class HashTable {
public:
list<int> vis[HASH];
void insert(int val) {
vis[val % HASH].push_back(val);
}
bool query(int val) {
for(auto num : vis[val % HASH]) if(num == val) return 1;
return 0;
}
void clear() {
for(int i = 0; i < HASH; i ++) vis[i].clear();
}
};
HashTable hashTable;
void bfs() {
queue<node> que;
que.push(u0), hashTable.insert(u0.getCode());
while(!que.empty()) {
node u = que.front();
que.pop();
for(int k = 0; k < 4; k ++) {
node v = u;
int nx = v.x + Fx[k][0], ny = v.y + Fx[k][1];
if(nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
swap(v.val[v.x][v.y], v.val[nx][ny]), v.x = nx, v.y = ny, v.path += Ord[k];
int hash = v.getCode();
if(hashTable.query(hash)) continue;
que.push(v), hashTable.insert(hash);
}
if(que.empty()) {
u.output();
cout << u.path << endl;
}
}
}
int main() {
cin >> kase;
for(int k = 1; k <= kase; k ++) {
for(int i = 0; i < 3; i ++) for(int j = 0; j < 3; j ++) {
cin >> u0.val[i][j];
if(u0.val[i][j] == 0) u0.x = i, u0.y = j;
}
u0.path.clear();
hashTable.clear();
cout << "Puzzle #" << k << "\n";
bfs();
cout << endl;
}
}
- 康托编码实现
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
const int Fx[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const int Fac[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
const string Ord = "ULDR";
class node {
public:
int val[3][3];
int x, y;
string path;
node() {}
int getCantor() const {
int res = 0;
for(int i = 0; i < 9; i ++) {
int small = 0;
for(int j = i + 1; j < 9; j ++) if(val[j / 3][j % 3] < val[i / 3][i % 3]) small ++;
res += small * Fac[8 - i];
}
return res;
}
void output() {
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j ++) cout << (j ? " " : "") << val[i][j];
cout << "\n";
}
}
};
int kase;
node u0;
bool vis[4000000];
void bfs() {
queue<node> que;
que.push(u0), vis[u0.getCantor()] = 1;
while(!que.empty()) {
node u = que.front();
que.pop();
for(int k = 0; k < 4; k ++) {
node v = u;
int nx = v.x + Fx[k][0], ny = v.y + Fx[k][1];
if(nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
swap(v.val[v.x][v.y], v.val[nx][ny]), v.x = nx, v.y = ny, v.path += Ord[k];
int hash = v.getCantor();
if(vis[hash]) continue;
que.push(v), vis[hash] = 1;
}
if(que.empty()) {
u.output();
cout << u.path << endl;
}
}
}
int main() {
cin >> kase;
for(int k = 1; k <= kase; k ++) {
for(int i = 0; i < 3; i ++) for(int j = 0; j < 3; j ++) {
cin >> u0.val[i][j];
if(u0.val[i][j] == 0) u0.x = i, u0.y = j;
}
u0.path.clear();
memset(vis, 0, sizeof(vis));
cout << "Puzzle #" << k << "\n";
bfs();
cout << endl;
}
}
四、归纳
- 最终测试了一下，3种方法都能在vjudge中通过，其中set方法用时1660ms，哈希法和康托法差不多，用时分别为1060ms和1100ms.
- 这道题还让我学会了一点，就是C++课上学的class写法也可以大胆地用起来呀！一直以来都是只是用struct存放一些值而已，不过在复杂的题目中，class能意外地让代码变得清晰起来。使用class的话，简单的将struct改成class，然后加一个public将所有变量、方法暴露出来即可，然后还是实例化一个对象出来使用比较不容易出错。
京公网安备 11010502036488号